0
$\begingroup$

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!

$\endgroup$
1
  • $\begingroup$ Note that you don't need 2 as a base case. $\endgroup$ – Stefan Hante Oct 20 '15 at 22:10
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks, i finished it off! However I'm confused what exactly should go inside my inductive hypothesis? Should I be stating for $n = k$, $T(k) = 2(4^{k}) + (-1)(-3^{k})$? Then can we do the "swap" using that in the inductive step $\endgroup$ – Xian Oct 21 '15 at 20:04
  • $\begingroup$ @Xian: Let $P(k)$ be the statement that $T(k)=2\cdot4^k+(-1)(-3^k)$; then your induction hypothesis is that $P(k)$ holds for all $k<n$, and you’re proving that $P(n)$ holds. This is the form of induction often called strong induction. $\endgroup$ – Brian M. Scott Oct 21 '15 at 20:21
1
$\begingroup$

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}

$\endgroup$
2
  • $\begingroup$ It looks like we are going to get $2(4^{n}) + (3)((-3)^{n-1})$. Is this basically the "n+1" of the original, since the terms are T(n-1) and T(n-2)? so it becomes T(n) and T(n-1) to prove it with induction? Sorry if that's not clear, I'm still new on this subject $\endgroup$ – Xian Oct 20 '15 at 22:42
  • $\begingroup$ You need to prove the formula for $T(n)$, using the formula for $T(n-1)$ and $T(n-2)$. $\endgroup$ – Stefan Hante Oct 20 '15 at 23:04
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.