Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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|cite|improve this answer

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|cite|improve this answer


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|cite|improve this answer

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.