Define a sequence $a_0 = 2$ and $a_1 = 4$ and $a_n := 2a_{n-1} - a_{n-2} + 6 $ for $ n \geq 2.$ Prove that $a_n = 3n^2 - n + 2.$

Question

Proof.

We proceed by strong induction on n. Observe that $a_0 = 2 = 3(0)^2 - 0 + 2$ and $a_1 = 4 = 3(1)^2 - 1 + 2.$

Assume that there is an integer k such that $a_j = 3j^2 - n + 2$ for all $2 < j < k.$

Then $a_{k+1} = 2a_k - a_{n-1} + 6$

Unsure of how to get right side equal to $a_n$. There is an example in the textbook but I couldn't wrap my head around how they got past this part.

Answer 1

Now, by the assumption of the induction: $$a_n=2(3(n-1)^2-(n-1)+2)-(3(n-2)^2-(n-2)+2)+6=3n^2-n+2.$$

Answer 2

$a_0 = 2$, $a_1 = 4$

$a_n = 2a_{n-1}-a_{n-2}+6$ Write out the other forms of the recurring equation

$a_{n-1} = 2a_{n-2}-a_{n-3}+6$ $a_{n-2} = 2a_{n-3}-a_{n-4}+6$ $a_{n-3} = 2a_{n-4}-a_{n-5}+6$ etc...

Use these other form to create a standard form, by combining them such that I would only make of only $a_0$ and $a_1$ to extract the values of $a_n$

$a_{n} £ a_{n-k+1}, a_{n-k}$

$a_{n} = 2*a_{n-1}-a_{n-2}+6$ $a_{n} = 3*a_{n-2}-2*a_{n-3}+6*2+6$ $a_{n} = 4*a_{n-3}-3*a_{n-4}+6*3+6*2+6$ $a_{n} = 5*a_{n-4}-4*a_{n-5}+6*4+6*3+6*2+6$ $a_{n} = 6*a_{n-5}-5*a_{n-6}+6*5+6*4+6*3+6*2+6$ It's not hard to see the process

$a_{n} = k*a_{n-k+1}-(k-1)*a_{n-k}+6*\sum_{i=1}^{k-1} i$

Say $n= k$

$a_{k} = k*a_{1}-(k-1)*a_{0}+6*\sum_{i=1}^{k-1} i$

$a_{k} = 4*k-2*(k-1)+6*\sum_{i=1}^{k-1} i$

$a_{k} = 4*k-2*k+2+6*(k-1)*k*(1/2)$

$a_{k} = 4*k-2*k+2+3*k*(k-1)$

$a_{k} = 4*k-2*k+2+3*k^2-3*k$

$a_{k} = 3*k^2-k+2$