On a previous data structures and algorithm exam, I was asked the following question:
Consider the following sequences of numbers which are the relative lengths of the subdivisions on a ruler.
Write a recurrence relation that describes the length of the ruler as a function of n and solve it.
1 (when n=1)
121 (when n=2)
1213121 (when n=3)
121312141213121 (when n=4)
The answer I put was:
T(n)=2^(n)-1
However, this turned out to be incorrect and I am having trouble coming up with the right answer. If anyone could provide some insight, that would be brilliant! Thanks!
If you're building up the string itself you could express it this way:
S(n) := S(n-1)nS(n-1) where S(1) := 1
The length is similar:
L(n) := L(n-1) + 1 + L(n-1) = 2L(n-1) + 1
A recurrence relation is expressed in terms of the preceding term and that's why your answer was wrong.
https://courses.engr.illinois.edu/cs573/fa2010/notes/99-recurrences.pdf