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
    Commented Oct 20, 2015 at 22:10

3 Answers 3

Reset to default
2
$\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
    Commented Oct 21, 2015 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
    Commented Oct 21, 2015 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
    Commented Oct 20, 2015 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
    Commented Oct 20, 2015 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .