Finding the closed form of a recursive formula using repeated substitution

Question

I am trying to find the closed form of the following recursive function by repeated substitution: $$T(n)=\left\{\begin{matrix} 7 & n=0\\ 25 & n=1\\ 2T(n-1)+3T(n-2) & n\ge 2 \end{matrix}\right.$$

So far, I have: $$ \begin{align} T(n)&=2T(n-1)+3T(n-2)\\ &=2[2T(n-2)+3T(n-3)]+3[2T(n-3)+3T(n-4)]=2^2T(n-2)+2\cdot2\cdot3T(n-3)+3^2T(n-4)\\ &=2^3 T(n-3) + 3 \cdot 2^2 \cdot 3T(n-4) + 3 \cdot 2 \cdot 3^2 T(n-5) + 3^3 T(n-6)\\ &\vdots\\ &=\sum_{i=0}^{k}\binom{k}{i}2^{k-i}\cdot 3^{i}\cdot T(n-(k+i)) \end{align} $$ where $k$ is the number of substitutions made.

I am not sure how to get from this to a closed form. I know I am supposed to find a pattern, but I do not see one. How can I get the closed form of this function using repeated substitution?

Answer 1

Consider the corresponding quadratic equation $x^2-2x-3=0$. It has two roots $-1, 3$. So the general formula is $T(n)=a(-1)^n+b3^n$ for some constant $a,b$. Plugging $n=0, 1$ you get

$$7=a+b\\ 25= -a+3b$$

So $4b=32, b=8, a=-1$. The answer: $T(n)=-(-1)^n+8\cdot 3^n$.

Answer 2

Let $V$ be the vector space of all functions $f:\mathbb N\to\mathbb R$ such that $f(n)=2f(n-1)+3f(n-2)$. These are completely determined by the values of $f(0)$ and $f(1)$, so $\dim V=2$.

Let $\alpha_1,\alpha_2$ be solutions to $x^2-2x-3=0$. Then $\{n\mapsto\alpha_1^n\},\{n\mapsto \alpha_2^n\}\in V$ and are linearly independent, so form a basis. Importantly, these functions both have a nice closed form. Thus, any function $f\in V$ (and in particular your function $T$) can be expressed as $f(n)=a\alpha_1^n+b\alpha_2^n$, for $a,b\in\mathbb R$, giving it a closed form.