RECURRENCES 1

Question

How to solve ?

T(1) = 8, and for all n ≥ 2, T(n)=3T(n − 1) − 15.

 

My Attempt:

T(n)=3T(n − 1) - 15 (after one substitution)

= 3(3T(n − 2) - 15) - 15

= 9T(n − 2) - 15 · 3 -15 (after two substitutions)

= 9(3T(n − 3) - 15) - 15 · 3 - 15

= 27T(n − 3) - 15 · 9- 15 · 3 - 15 (after three substitutions).

After this How to approach ?

Answer 1

What each substitution is doing?

Each substitution is giving us a new way of expressing $T(n)$ in terms of some $T(n - k)$ where $k$ is an integer between $1$ & $n$.

We know the value of $T(1)$ so we should try to write $T(n)$ in terms of $T(1)$.

It is not possible to start with $T(n)$ & exhaustively back substitute until we reach $1$, since $n$ is unknown to us.

So we have to observe & generalise the changing pattern in the expression for $T(n)$.

To observe the pattern, instead of multiplying numbers it would be better to keep them apart.

so we get

$T(n) = 3^1 \cdot T(n - 1) - \left ( 3^0 \times 15 \right )$

after first substitution.

$T(n) = 3^{2} \cdot T(n - 2) - \left ( 3^1 \times 15 \right ) - \left ( 3^0 \times 15 \right )$

after second substitution.

$T(n) = 3^{3} \cdot T(n - 3) - \left ( 3^{2} \times 15 \right ) - \left ( 3^1 \times 15 \right ) - \left ( 3^0 \times 15 \right )$

after third substitution.

$T(n) = 3^{4} \cdot T(n - 4) -\left ( 3^{3} \times 15 \right ) - \left ( 3^{2} \times 15 \right ) - \left ( 3 \times 15 \right ) - \left ( 3^0 \times 15 \right )$

after fourth substitution and so on.

$\cdots \cdots$

So after $k^{th}$ substitution we will get

$T(n) = 3^{k} \cdot T(n - k) -\left ( 3^{k} \times 15 \right ) - \left ( 3^{k - 1} \times 15 \right ) \cdots - \left ( 3^{2} \times 15 \right ) - \left ( 3^1 \times 15 \right ) - \left ( 3^0 \times 15 \right )$

we can also write it as

$T(n) = 3^{k} \cdot T(n - k) - 15\cdot \left ( \sum_{i = 0}^{k -1} 3^i\right )$

On summing up the geometric series we get,

$T(n) = 3^{k} \cdot T(n - k) - 15\cdot \frac{\left ( 3^{k} - 1 \right )}{2}$

We know $T(1) = 8$, so we must choose $k$ such that  

$T(n - k) = T(1)$

or $\left ( n - k \right ) = 1$

$\Rightarrow k = \left( n -1 \right) $

On putting $k = \left ( n -1 \right )$ in the generalized recurrence, we get:

$T(n) = 3^{\left ( n -1 \right )} \cdot T(n - \left ( n -1 \right )) - 15\cdot \frac{\left ( 3^{\left ( n -1 \right )} - 1 \right )}{2}$

$\Rightarrow T(n) = 3^{\left ( n -1 \right )} \cdot T(1) - 15\cdot \frac{\left ( 3^{\left ( n -1 \right )} - 1 \right )}{2}$

$\Rightarrow T(n) = \left( 3^{\left ( n -1 \right )} \times 8 \right) - 15\cdot \frac{\left ( 3^{\left ( n -1 \right )} - 1 \right )}{2}$

$\Rightarrow T(n) = \left( 8 \times 3^{\left ( n -1 \right )} \right) - \left ( 7.5 \times 3^{\left ( n -1 \right )} \right ) +7.5$

$\Rightarrow T(n) = \left( 0.5 \times 3^{\left ( n -1 \right )}  \right) 
+7.5$

$\Rightarrow T(n) = \frac{1}{2}\left(  3^{\left ( n -1 \right )} +15 \right)$

Answer 2

T(n)=3T(n − 1) - 15 (after one substitution)

= 3(3T(n − 2) - 15) - 15

= 9T(n − 2) - 15 · 3 -15 (after two substitutions)

= 9(3T(n − 3) - 15) - 15 · 3 - 15

= 27T(n − 3) - 15 · 9- 15 · 3 - 15 (after three substitutions).

...........

=3^kT(n - k) - 15(3^k+3^k-1+.............3²+3¹+3⁰)

=3^n-1T(1) - 15 ((3^n-1 -1)/(3-1))

=3^n-1 . 8 - 15/2(3^n-1 -1)

=3^n-1(8 - 15/2)+15/2

=1/2(3^n-1+15)