Find the closed form for the following, then prove by strong induction:
$$T(n) = \begin{cases} 1\quad &\text{ if } n = 0 \\
11\quad &\text{ if } n = 1 \\ T(n-1) + 12T(n-2) & \text{ otherwise } \end{cases}$$
I managed to solve for a closed-form expression of the recurrence, which is:
$2(4^n) + (-1)(-3)^n$, however I'm stuck on proving it by strong induction. The closed-form expression does seem to work when I check the outputs.
I'm guessing you'll have 0, and 1 as your base cases, but I'm not sure how to continue with this. I tried doing $2(4^{k+1} + (-1)(-3^{k+1})$ and arrived at $2(4^{k})(4) + (-1)(-3^{k})(-3)$, but unsure how to continue. Do I substitute the original inductive hypothesis at this point?
Thanks!
Best Answer
Since the recurrence is second-order, you need only two base cases, $n=0$ and $n=1$.
For the induction step you want to assume that $n\ge 2$, $T(k)=2\cdot4^k+(-1)(-3)^k$ for $k<n$ and show that $T(n)=2\cdot4^n+(-1)(-3)^n$. Use the recurrence:
$$\begin{align*} T_n&=T(n-1)+12T(n-2)\\ &=2\cdot 4^{n-1}+(-1)(-3)^{n-1}+12\left(2\cdot4^{n-2}+(-1)(-3)^{n-2}\right)\\ &=2\cdot 4^{n-1}+24\cdot4^{n-2}+(-1)\left((-3)^{n-1}+12(-3)^{n-2}\right)\\ &=2\cdot4^{n-1}+6\cdot4^{n-1}+(-1)\left((-3)^{n-1}-4(-3)^{n-1}\right)\;, \end{align*}$$
where the very first step uses the induction hypothesis. See if you can finish it off from here.