Prove that a recurrence relation (containing two recurrences) equals a given closed-form formula.

Question

Prove that $a_n = 3a_{n-1} - 2a_{n-2} = 2^n + 1$ , for all $n \in \mathbb{N}$ , and $a_1 = 3$ , $a_2 = 5$ , and $n \geq 3$

Basis:
$a_1 = 2^1 + 1 = 2 + 1 = 3$ $\checkmark$
$a_2 = 2^2 + 1 = 4 + 1 = 5$ $\checkmark$

Inductive Hypothesis:
$a_k = 2^k + 1$ , where $n = k$
$a_k = 3a_{k-1} - 2a_{k-2}$

Inductive Step:

$$\begin{align} \ a_{k+1} & = 3a_k - 2a_{k-1} \\ & = 3(2^k + 1) - 2(2^{k-1} + 1) \\ & = \color{red}{6^k} + 3 - \color{red}{4^{k-1}} - 2 \\ & = \color{red}{6^k} - \color{red}{4^{k-1}} + 1 \end{align}$$

Now, the $ + 1$ looks very promising, but $6^k - 4^{k-1}$ makes me sick. Anyone have some good hints? That second recurrence ( $2a_{n-2}$ ) seems to be stumping me.

Answer 1

$$3\cdot 2^k - 2\cdot 2^{k-1}= 3\cdot 2^k -2^k=2^k(3-1)=2^k\cdot2=2^{k+1}$$

Notice that $$ 3\cdot 2^k = 2^k + 2^k + 2^k$$

While $$ 6^k=(3 \cdot 2)^k=3^k\cdot 2^k=2^k + 2^k ....... + 2^k$$

The last line shows $2^k$ being added $3^k$. There is a way to show this better in latex (a bracket under the ellipses) but I don't know how.

Answer 2

Inductive Hypothesis:
$a_k = 2^k + 1$ , where $n=k$ , to show:
$$\begin{align} \ a_{k+1} & = 2^{k+1} + 1 \\ \end{align}$$

Inductive Step:

$$\begin{align} \ a_{k+1} & = 3a_{(k+1)-1} - 2a_{(k+1)-2}\\ & = 3a_k - 2a_{k-1} \\ & = 3(2^k + 1) - 2(2^{k-1} + 1) \\ & = 3(2^k) + 3 - 2(2^{k-1}) - 2 \\ & = (2^k + 2^k + 2^k) - (2^{k-1} + 2^{k-1}) + 3 - 2 \\ & = (2^{k+1} + 2^k) -(2^k) + 1 \\ & = 2^{k+1} + 2^k - 2^k + 1 \\ & = 2^{k+1} + 1 \\ \end{align}$$

Gee, I might be having more fun formatting the MathJax than I am solving the math. Oh well, thanks to all!