$Determine the Closed Form of a Recurrance Relation$

Question

Using this iteration method, I need to figure out the closed form for this reccurance relation:

T(n) = 2T(n - 10) + 3, for n > 11, T(n) = 5 for n <= 10

The answer is to be expressed exactly, using equality and not a bound or asymptomatic notation.

you can assume the following:

n = 10l +1 for some positive integer l
the expression does not need to be completely simplified, you can use either or both n and l in the solution

What i've gathered so far is the first 10 numbers in the sequence are 5, the next 10 numbers are equal to (2*previous number) + 3, so 13, and so on for every 10 terms. (correct?)

5 5 5 5 5 5 5 5 5 5 13 13 13 13 13 13 13 13 13 13 29 29 29 29 29 29 29 29 29 29 ...

Help in finding the closed form of this relation? preferably in terms of n , l and maybe both?

Graph Theory Algebra Sequences and Series

Deleted Account

Report

Answer 1

Answers can be viewed only if

The questioner was satisfied and accepted the answer, or
The answer was disputed, but the judge evaluated it as 100% correct.

View the answer

Let $n=10k+1$, let $T'(k) \coloneqq T(10k+1)$, then (as you said) it is enough to give a formula for $T'(k)$.

Let $T''(k) \coloneqq T'(k)+3$. We have $T'(k+1) = 2 \cdot T'(k) + 3$, so $T'(k+1) + 3 = 2 \cdot T'(k) + 6$, or equivalently, $T''(k+1) = 2 \cdot T''(k)$.

Now, $T''(0) = T'(0) + 3 = T(10 \cdot 0 + 1) + 3 = T(1) + 3 = 5 + 3 = 8$. Moreover, $T''(k) = 2 \cdot T''(k-1) = 2^2 \cdot T''(k-2) = \dots = 2^k \cdot T''(0) = 2^{k+3}$.

It follows that, if $n=10k+1$, then $T(n) = T'(k) = T''(k) - 3 = 2^{k+3} - 3$. In general, if $n = 10k+h$ for $1 \leq h \leq 10$, we still have $T(n) = 2^{k+3} - 3$.

As you already checked by hand, $T(1) = 2^{3-0} - 3 = 5$, $T(11) = 2^{1+3} - 3 = 13$, $T(21) = 2^{2+3} - 3 = 29$, and so on.

Alessandro Iraci

$Determine the Closed Form of a Recurrance Relation$

Answer

Related Questions

Search