Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$$

share|improve this question
add comment

3 Answers

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$$

share|improve this answer
add comment

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. $$

share|improve this answer
add comment


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.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.