Finding a closed form for the recursively defined function using the substitution method.

Question

This is a question from a problem set I had to do for one one of my courses. The following recursively defined function is given \begin{equation*} T(n) = \begin{cases} 1, & if \ n=0 \\ 4, & if \ n=1 \\ 4T(n-1)-4T(n-2), & if\ n > 1 \end{cases} \end{equation*} and we had to find a closed form for it using the substitution method. This is what I did

Step 1: substitution

$T(n) = 4T(n-1)-4T(n-2)$

$T(n-1) = 4T(n-2)-4T(n-3)$

$T(n-2) = 4T(n-3)-4T(n-4)$

$T(n-3) = 4T(n-4)-4T(n-5)$

$T(n-4) = 4T(n-5)-4T(n-6)$

$T(n-5) = 4T(n-6)-4T(n-7)$

$k=2$

$T(n) = 16T(n-2)-32T(n-3)+16T(n-4)$

$k=3$

$T(n) = 64T(n-3)-192T(n-4)+192T(n-5)-64T(n-6)$

$k=4$

$T(n) = 256T(n-4)-1024T(n-5)+1536T(n-6)-1024T(n-7)+256T(n-8)$

$k=5$

$T(n) = 1024T(n-5)-5120T(n-6)+10240T(n-7)-10240T(n-8)+ 5120T(n-9)-1024T(n-10)$

Step 2: guess the recurrence

so what I noticed was that the coefficient in front of each functions corresponded to the terms in pascals triangle multiplied by $4^n$ so I ended up with the following potential closed form.

$$T(n) = \sum_{r=0}^{i = n+1} (-1)^r\binom nr (4^k)*T(n-(k+r))$$ after solving for $k$ I got

$k = n-r-1$ for $t(1)$ $$T(n) = \sum_{r=0}^{i = n+1} (-1)^r\binom nr \left(4^{n-r}\right)$$

$k=n-r$ for $t(0)$ $$T(n) = \sum_{r=0}^{i = n+1} (-1)^r\binom nr \left(4^{n-r-1}\right)$$

from here we have to us induction to prove that our potential closed form is true (base cases don't hold for my formulas) my question is

1) Is my approach to this question correct how would you have done it ?

2) Why can't we have a summation as part of our closed form ?

3) How do I get my closed form when I have a summation (get rid of it) ?

4) Does there exist a recursively defined function that does not have a closed form?

That is all thank you for your time and help.

Answer 1

$$\begin{align} T(n)&=4T(n-1)-4T(n-2)\\ \overbrace{T(n)-2T(n-1)}^{U(n)}&=2\overbrace{[T(n-1)-2T(n-2)]}^{U(n-1)}\\ U(n)&=2U(n-1)\\ &=2^2U(n-2)\\ &\vdots\\ &=2^{n-1}U(1)\\ &=2^{n-1}[\overbrace{T(1)}^4-2\overbrace{T(0)}^1]\\ &=2^n\\ T(n)-2T(n-1)&= 2^n&&\color{red}{(*)}\\ 2T(n-1)-4T(n-2)&=2\cdot 2^{n-1}=2^n\\ 4T(n-2)-8T(n-3)&=2^2\cdot 2^{n-2}=2^n\\ &\vdots\\ &\vdots\\ 2^{n-1}T(1)-2^nT(0)&=2^{n-1}2=2^n\\ \text{Summing:}\qquad\qquad\qquad\qquad\qquad&\\ T(n)-2^n\overbrace{T(0)}^1&=n\cdot 2^n\\ T(n)&=(n+1)2^n\quad\blacksquare \end{align}$$

---

Alternative version using insight from here:

From $\color{red}{(*)}$, we have $$\begin{align}T(n)&=2T(n-1)+2^n\\ \div 2^n:\qquad\qquad\qquad \frac {T(n)}{2^n}&=\frac {T(n-1)}{2^{n-1}}+1\\ \text{Put $U_n=\frac {T(n)}{2^{n}}$}:\qquad\qquad\qquad\ U_n&=U_{n-1}+1\\ \text{Telescoping down to $U_1-U_0$}:\qquad\qquad\qquad U_n&=U_0+n\\ \frac {T(n)}{2^n}&=\frac {T(0)}{2^0}+n=1+n\\ T(n)&=(n+1)2^n\quad\blacksquare\end{align}$$

Answer 2

Look for solutions of the form $T(n) \propto \lambda^n$. When you find a repeated root in such solutions, look for additional solutions of the form $T(n) \propto n\lambda^n$. Notice that the problem is linear so solutions can be linearly combined to form other solutions.