CODEWITHSUNDEEP
relationrecurrence
busebd12
busebd12

Reputation: 1007

Recurrence relation that describes the length of a ruler

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!

Upvotes: 2

Views: 224

Answers (1)

shawnt00
shawnt00

Reputation: 17915

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

Upvotes: 2

Related Questions