Strong Induction (verify solution of linear recurrence)

Question

I am trying to prove a statement using strong induction but I seem to be getting stuck. I don't know if did something wrong or I am just not recognizing an opportunity for factoring/how to factor numbers with rational exponents. Here is the prompt:
Let $ a_0, a_1, a_2, ...$ be a sequence such that $a_0 = 2, a_1 = 6$ and $a_k = 6a_{k−1} − 8a_{k−2}$ for $k ≥ 2.$ Prove that $a_n = 2^n(2^n + 1)$ for all $n ≥ 0. $

Answer 1

Suppose the statement holds for all $n<k$. Let's look at $a_k$.

By definition, $a_k=6a_{k-1}-8a_{k-2}$.

What does the induction hypothesis tell you about $a_{k-1}$?

What does the induction hypothesis tell you about $a_{k-2}$?

---

Note that for this to really make sense, I need $k\ge 2$ (since $a_0$ and $a_1$ are defined differently). So really, the full proof needs to also include calculations for $k=0$ and $k=1$; but that's not hard.

Answer 2

If $a_k = 6a_{k−1} − 8a_{k−2} $ and $a_n = 2^n(2^n + 1) $ for $n=k-1$ and $k-2$, then

$\begin{array}\\ a_k &= 6a_{k−1} − 8a_{k−2}\\ &= 6(2^{k-1}(2^{k-1} + 1)) − 8(2^{k-2}(2^{k-2} + 1))\\ &= 6(2^{2k-2}+2^{k-1}) − 8(2^{2k-4}+2^{k-2})\\ &= 3(2^{2k-1}+2^{k}) − (2^{2k-1}+2^{k+1})\\ &= 3\cdot 2^{2k-1}+3\cdot 2^{k} − 2^{2k-1}-2^{k+1}\\ &= 2\cdot 2^{2k-1}+2^{k+1}+ 2^{k}-2^{k+1} \qquad\text{(using }3=2+1)\\ &= 2^{2k}+ 2^{k}\\ &= 2^{k}(2^{k}+1)\\ \end{array} $

and we are done.

Not sophisticated, but not trivial.

Note that we need the result true for k-1 and k-2 to show that it is true for k.

I would call this "weak strong induction" since I usually interpret "strong induction" to assuming that it is true for all j < k, not just the preceding two values.