Non-homogeneous Recurrence relations

I want to solve these recurrence relations with the initial conditions given. I know how to solve linear non-homogeneous recurrence relations with constant coefficients.

$$(a)\ \ {a_n}^2=2{a_{n-1}}^2+1 ,a_0=1$$ $$(b)\ \ a_n=-n a_{n-1}+n!,a_0=1$$

-

For the first one make the substitution $b_n=a_n^2$

For the second one make the substitution $b_n=\frac{(-1)^na_n}{n!}$, to get: $$(-1)^nn!b_n=-n(-1)^{n-1}(n-1)!b_{n-1}+n!$$ Now divide by $(-1)^nn!$, to get: $$b_n=b_{n-1}+(-1)^n$$

-

For the non linear one, put $a^2_n = z_n$ which implies

$$a^2_n=a^2_{n-1} + 1 \implies z_n=z_{n-1}+1\implies \dots.$$

-

HINTS:

It never hurts to gather some data. For (b), calculate the first few values of $a_n$: $a_1=-1+1=0$, $a_2=2!$, $a_3=-3\cdot2!+3!=0$, $a_4=4!$, $a_5=-5\cdot4!+5!=0$, and $a_6=6!$. In tabular form:

$$\begin{array}{rcc} n:&0&1&2&3&4&5&6\\ \hline a_n:&1&0&2!&0&4!&0&6! \end{array}$$

That’s a pretty obvious pattern, especially when you recall that $0!=1$. Make the obvious guess, and try to prove it by induction.

Now try the same approach with (a): $a_1^2=2\cdot1^2+1=3$, so $a_1=\sqrt3$; $a_2^2=2\cdot3+1=7$, so $a_2=\sqrt7$; $a_3^2=2\cdot7+1=15$, so $a_3=\sqrt{15}$; and $a_4^2=2\cdot15+1=31$, and $a_4=\sqrt{31}$. The sequence $1,3,7,15,31$ should suggest a solid conjecture as to the value of $a_n$ in general, and you can then prove it by induction.

-