linear recurrence relation problem

Question

$$a(n) = (n+1) a(n-1),$$ $$a(0) = 5$$

I've been thinking about this problem for a long while but I do not know how to even start.

Answer 1

Hint:

The problem is nonlinear but in each iteration, you multiply a number that is bigger than the previous number by $1$. Think along terms involving factorial.

Try to prove the following:

$$a(n)=(n+1)!5$$

Try induction.

Answer 2

substituting n for n+1 we get, $a(n+1) = (n+2)*a(n)$ intput $a(0)=5$ and we get $a(1) = (2)*5 = 10$,$a(2)=3*a(1)=3*2*5$ and so on... to get $a(n)=(n+!)!(5)$

Answer 3

Because $a_n$ looks something like $na_{n-1}$, a good substitution to try is $$b_n = \frac{a_n}{(n+k)!}$$ When you do this, you get $b(0)=5k!$ and $$ (n+k)!b_n = (n+1) (n+k-1)! b_{n-1} $$ We are free to choose $k$; we would love to be able to say that $(n+k)! = (n+1) (n+k-1)!$. This works out if we choose $k=1$ so let $a_n = b_n(n+1)!$ and then $b(0)=5$ and for all $n>0$ $$ b_n = b_{n-1} $$ Thus $$ a_n = 5(n+1)! $$

Answer 4

Mark Fischler’s approach is very nice if you see it, but this is a first-order recurrence, so if you don’t, you can always try ‘unwrapping’ the recurrence:

$$\begin{align*} a_n&=(n+1)a_{n-1}\\ &=(n+1)na_{n-2}\\ &=(n+1)n(n-1)a_{n-3}\\ &\;\;\vdots\\ &=a_{n-k}\prod_{\ell=n-k+2}^{n+1}\ell\\ &\;\;\vdots\\ &=a_0\prod_{\ell=2}^{n+1}\ell\\ &=5(n+1)! \end{align*}$$

Since the expression for $a_{n-k}$ was obtained by recognizing the pattern, this isn’t entirely rigorous, and the final expression should now be proved by induction on $n$.

If that seems a little abstract, try simply computing some values:

$$\begin{align*} &a_0=5\\ &a_1=a_0\cdot 2=5\cdot2\\ &a_2=a_1\cdot 3=5\cdot2\cdot3\\ &a_3=a_2\cdot5=5\cdot 2\cdot3\cdot4 \end{align*}$$

At this point it’s not hard to guess that

$$a_n=5\cdot2\cdot3\cdot4\cdot\ldots\cdot(n+1)=5(n+1)!\;,$$

and it can be proved by induction on $n$.