1

I would like to find the particular solution the following recurrence relation.

$$a_{n}-a_{n-1} = 2(n-1), a_0 = 2$$

By inspection, we would try with $a_n^{(p)} = Bn+C$. When substituting this in the recurrence relation we get

$$Bn+C = B(n-1)+C+2(n-1)$$

and this implies $B=B+2$, which is absurd. What's wrong with this?

Sorry, if this question is answered before.

Kumara
  • 706
  • Your "inspection" seems to be off. Indeed, if $a_n = Bn+C$, then $a_n - a_{n-1}$ will have to be a constant, so this ansatz is doomed from the outset. – stochasticboy321 Sep 15 '16 at 17:06
  • 1
    What looks wrong to me is your assumption that a degree-one polynomial might be a solution, even though the first difference is increasing – Henry Sep 15 '16 at 17:07
  • 1
    What's wrong with this? It means that a linear solution doesn't exist. You may try a 2nd degree $A n^2 + B n + C$ polynomial next. Or simply write down the first few terms of the sequence explicitly, and recognize that it's related to a sum of consecutive numbers. – dxiv Sep 15 '16 at 17:07
  • prove by induction that $$a_n=2-n+n^2$$ – Dr. Sonnhard Graubner Sep 15 '16 at 17:13

1 Answers1

1

If you use that method, you’ll need to look for a quadratic solution, not a linear solution. However, there are easier ways. Notice that if you add consecutive differences of the form $a_{k+1}-a_k$, they telescope. For instance,

$$(a_3-a_2)+(a_2-a_1)+(a_1-a_0)=a_3-a_0\;.$$

Thus,

$$\begin{align*} a_n-a_0&=(a_n-a_{n-1})+(a_{n-1}-a_{n-2})+(a_{n-2}-a_{n-3}+\ldots+(a_1-a_0)\\ &=\sum_{k=0}^{n-1}(a_{k+1}-a_k)\\ &=\sum_{k=0}^{n-1}2k\\ &=2\sum_{k=0}^{n-1}k\;, \end{align*}$$

and from there it’s straightforward to get a closed form for $a_n$.

Brian M. Scott
  • 616,228
  • Thank you for this alternate solution. There is a typo in the last but one expression. I think it should be $2k$ instead of $2a_k$. – Kumara Sep 16 '16 at 03:51
  • @Kumara: You're absolutely right, and in the last expression as well; thanks for catching that. You're welcome. – Brian M. Scott Sep 16 '16 at 03:55