0

from here

Consider the sequence $5, 0, -8, -17, -25, -30, \dots$ given by the recursion shown.

$$a_0 = 5 \\ a_n = a_{n - 1} + n^2 - 6$$

Is this correct? I can calculate $a_1$:

$$a_1 = 5 + 1^2 - 6 = 0$$

But i can't calculate $a_2$:

$$a_2 = 0 + 2^2 - 6 = -2$$

But $-2 \not= -8$ (I also get a mistake when $n>2$)

What am i doing wrong? Or Is there a mistake on that website?

Thomas Russell
  • 10,425
  • 5
  • 38
  • 66
DrStrangeLove
  • 801
  • 2
    Given the recurrence formula, your computations are correct. And the initial sequence you gave is not this one. – Julien Mar 06 '13 at 18:36
  • That web site is incorrect. $a_n-a_{n-1}=n^2-6$. For $n\ge3$ difference is supposed to be positive. Which it is not in the sequence given. – Maesumi Mar 06 '13 at 19:24

1 Answers1

1

Let's take out the heavy machinery... the recurrence is: $$ a_{n + 1} = a_n + (n + 1)^2 - 6 = a_n + n^2 + 2 n - 5 $$ We also have $a_0 = 5$.

Define the ordinary generating function: $$ A(z) = \sum_{n \ge 0} a_n z^n $$ By the properties of ordinary generating functions, we get ($D$ is $\frac{d}{dz}$): $$ \frac{A(z) - a_0}{z} = A(z) + ((zD)^2 + 2 z D - 5) \frac{1}{1 - z} $$ Solving for $A(z)$ and expanding in partial fractions: $$ A(z) = 11 \cdot \frac{1}{1 - z} - 5 \frac{1}{(1 - z)^2} - 3 \frac{1}{(1 - z)^3} + 2 \frac{1}{(1 - z)^4} $$ Thus the solution is given by: $$ \begin{align*} a_n &= 11 - 5 \cdot (-1)^n \binom{-2}{n} - 3 \cdot (-1)^n \binom{-3}{n} + 2 \cdot (-1)^n \binom{-4}{n} \\ &= \frac{2 n^3 + 3 n^2 - 35 n + 30}{6} \end{align*} $$ This because $\binom{-k}{n} = (-1)^n \binom{n + k - 1}{k - 1}$.

Maxima's help with the algebra is gratefully acknowledged. Typoes and brainoes are entirely my fault.

vonbrand
  • 27,812
  • closed form calculation (after recurrence relation) can be done in a more elegant way : $a_{n} = a_{n-1} + p(n-1)$ , $a_{n-1} = a_{n-2} + p(n-2)$ .. $a_{1} = a_{0} + p(0)$, $p$ being the quadratic polynomial. Now just add all these equations, and only $a_{n}$ survives on LHS with a cubic on the RHS – Five Mar 06 '13 at 19:50
  • @piyush, yes. But the technique above is applicable much more generally. – vonbrand Mar 06 '13 at 20:01