Proving a closed-form recurrence by induction

Question

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!

Answer 1

Just verify your solution for the cases 0, 1 gives the same results as the recurrence relationship. Then actually verify the recurrence by substitution. More than an induction is a verification you need to do.

Answer 2

All you need is probably

\begin{align} T(n-1) + 12T(n-2) &= 2\cdot4^{n-1} - (-3)^{n-1} + 12\cdot2\cdot4^{n-2} - 12\cdot(-3)^{n-2}\\ &= 2\cdot4^{n-1} - (-3)^{n-1} + 3\cdot2\cdot4^{n-1} + 4\cdot(-3)^{n-1} \\ &= (1+3)\cdot2\cdot4^{n-1} +(-1+4)\cdot (-3)^{n-1} \\ &= 4\cdot2\cdot4^{n-1} -(-3)\cdot (-3)^{n-1} \\ \end{align}

Answer 3

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.