The sequence $(a_n)_{n ∈ N}$ is given with $a_1=1$, $a_2=13$ and $a_{n+2}=a_{n+1}+6a_n$

Question

To prove that: $\sum_{i=1}^na_i = (3^{n+2}+(-2)^{n+2}-13)/6$, for every natural number $n \ge 1$.

I don't know how to start with...

Answer 1

Consider the characteristic function: $$ x^2=x+6 $$ and we have two distinct eigenvalues, namely $ x_1=3, x_2=-2 $. Therefore, $$ a_n=C_13^{n}+C_2{(-2)}^n $$ where $ C_1, C_2 $ are two constants. Plug in the initial values, we get: $$ \begin{cases} a_1=3C_1 -2C_2=1\\ a_2=9C_1+4C_2=13 \end{cases} $$ Hence we have $$ \begin{cases} C_1=1\\ C_2=1 \end{cases}\quad\text{and}\quad a_n=3^n+(-2)^n .$$

Thus $$ \begin{align}\sum_{i=1}^na_i&=\sum_{i=1}^n3^{i}+\sum_{i=1}^n(-2)^{i}\\ &=3\frac{3^n-1}{2}-2\frac{1-(-2)^n}{3}\\ &=\frac{3^{n+2}-9-4+(-2)^{n+2}}{6}\\ &=\frac{3^{n+2}+(-2)^{n+2}-13}{6}. \end{align}$$

Answer 2

Hint: The characteristic equation: $x^2-x - 6 = 0$ gives: $x = -2, 3$, thus the general solution is: $a_n = A\cdot (-2)^n + B\cdot 3^n$, and $a_1 = 1, a_2 = 13 \implies A = B = 1$. Thus $a_n = (-2)^n + 3^n$. Can you continue ? Can you find the geometric sums $\sum (-2)^n $, and $\sum 3^n$ ?

Answer 3

The hint. $$a_{n+2}+2a_{n+1}=3(a_{n+1}+2a_n).$$ Thus, $$a_{n+1}+2a_n=15\cdot3^{n-1}=5\cdot3^n.$$ Now, use the telescoping sum.

Answer 4

Inductions a little arithmetic intensive but still doable.

The things to keep in mind is to use "strong" induction in the induction step so that you assume the proposition is true for all $n \le k$ and not just for $n = k$.

And the insight is that if the proposition is true for all $n\le k$ then

$a_k = \sum\limits_{i=1}^k a_i -\sum\limits_{i=1}^{k-1} a_i= \frac {3^{k+2} + (-2)^{k+2} - 13}6 -\frac {3^{k+1} + (-2)^{k+1} - 13}6 $.

And so the induction step becomes a matter of showing:

$\sum\limits_{i=1}^{k+1} a_i = $

$(\sum\limits_{i=1}^k a_i) + a_{k+1} =$

$ (\frac {3^{k+2} + (-2)^{k+2} - 13}6) + a_k + 6a_{k-1} = $

$(\frac {3^{k+2} + (-2)^{k+2} - 13}6) + (\frac {3^{k+2} + (-2)^{k+2} - 13}6 -\frac {3^{k+1} + (-2)^{k+1} - 13}6) + 6(\frac {3^{k+1} + (-2)^{k+1} - 13}6 -\frac {3^{k} + (-2)^{k} - 13}6)$

is equal to $\frac {3^{k+3} + (-2)^{k+3}-13}6$.

And that's just arithmetic.

(Note: That induction step assume the proposition is true for $a_k$, that $a_{k-1}$ exists, and that the proposition is true for $a_{k-1}$, and that $a_{k+1}$ is being defined as though $k+1 \ge 3$. [In other words, the induction step is for $n=k\ge 2$.] So for base cases you must show the proposition is true for $n=1;a_1$ and for $n=2;a_2$.)

(That's just a matter of plugging values in.)