рекуррентное соотношение, которое описывает длину линейки

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) 

Ответ, который я поставил был:

T(n)=2^(n)-1 

Однако, это оказалось неправильным, и у меня возникли проблемы с правильным ответом. Если бы кто-нибудь мог дать некоторое представление, это было бы великолепно! Благодаря!

Answer 1

Если вы строите до самой струне, которую вы могли бы выразить это так:

S(n) := S(n-1)nS(n-1) where S(1) := 1 

Длина аналогична:

L(n) := L(n-1) + 1 + L(n-1) = 2L(n-1) + 1 

рекуррентное соотношение выражается в терминах предыдущего срока и поэтому ваш ответ был неправильным.

https://courses.engr.illinois.edu/cs573/fa2010/notes/99-recurrences.pdf