Inductive Proof Recursive Definition

Question

Using this recursive Definition:

$$a_{n} = \left\{\begin{matrix} 4 & n=1\\ a_{n-1}+4n-5 & n \geq 2 \end{matrix}\right.$$

I somehow have to prove using induction

$$a_{n} = 2n^{2} - 3n + 5, n\geq 1$$

Answer 1

Just for fun, let's solve this one using generating functions.

Define $A(z) = \sum_{n \ge 0} a_n z^n$. Write the recurrence as: $$ a_{n + 1} = a_n + 4 n - 1 $$ It is nicer starting with index 0, so use the recurrence "backwards" to get $a_0 = 5$.

Multiply the recurrence by $z^n$, sum over $n \ge 0$, and recognize: \begin{align} \sum_{n \ge 0} a_{n + 1} z^n &= \frac{A(z) - a_0}{z} \\ \sum_{n \ge 0} z^n &= \frac{1}{1 - z} \\ \sum_{n \ge 0} n z^n &= z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - z} \\ &= \frac{z}{(1 - z)^2} \end{align} to get: $$ \frac{A(z) - 5}{z} = A(z) + \frac{4 z}{(1 - z)^2} - \frac{1}{1 - z} $$ Solve for $A(z)$, and express as partial fractions: $$ A(z) = \frac{5 - 11 z + 10 z^2}{1 - 3 z + 3 z^2 - z^3} = \frac{4}{(1 - z)^3} - \frac{9}{(1 - z)^2} + \frac{10}{1 - z} $$ By the (extended) binomial theorem for $r \in \mathbb{N}$ it is: $$ (1 - z)^{-r} = \sum_{k \ge 0} \binom{-r}{k} (-1)^k z^k = \sum_{k \ge 0} \binom{k + r - 1}{r - 1} z^k $$ so that: $$ A(z) = \sum_{n \ge 0} \left( 4 \binom{n + 2}{2} - 9 \binom{n + 1}{1} + 10 \right) z^n $$ and thus: $$ a_n = 4 \binom{n + 2}{2} - 9 \binom{n + 1}{1} + 10 = \frac{4 (n + 2) (n + 1)}{2} - \frac{9 (n + 1)}{1} + 10 = 2 n^2 - 3 n + 5 $$