Recursive definitions - cannot figure this one out

Question

I need to find a recursive solution to the below problem.

$$a_n=n(n-1)$$ for $n \in \mathbb{N}$

Calculating some values gives

\begin{align*} a_1&= 1\cdot (0)=0\\ a_2&= 2\cdot (2-1)=2\\ a_3&= 3\cdot(3-1)=6\\ a_4&= 4\cdot (4-1)=12\\ a_5&= 5\cdot(5-1)=20\\ a_6&= 6\cdot(6-1)=30 \end{align*}

I came up with $a_n=a_{n-1} + 2\cdot(n-1)$. This seems to work for all values. Is this correct?

You're looking for a recurrence relation that defines $a_n$, like $a_{n+1} = 2n + a_n$, $a_1 = 0$? — Cocopuffs, Aug 24 '13 at 20:31
his profile says he was not seen for past 28 minutes ago but this question was asked 21 minutes ago .contradiction.But anyway down voting doesn't make sense . may be he is new and doesn't know to edit . — Harish Kayarohanam, Aug 24 '13 at 20:40
This. I also wasn't able to get back online until today. Updated. — user797963, Aug 25 '13 at 16:11

score 3 · Accepted Answer · answered Aug 25 '13 at 18:40

Note that the recurrence relation is not unique. You can easily write

$$a_{n+1}-a_n=n(n+1)-n(n-1) = 2n,$$ resulting in the $a_{n+1}=a_n+2n$, $a_1=0$ as you have already established.

On the other hand, you can write a second order relation, because $$a_{n+2}-2a_{n+1}+a_n = (n+1)(n+2)-2n(n+1)+n(n-1) = 2,$$ giving us a scheme $a_{n+2}=2a_{n+1}-a_n+2$, $a_1=0$, $a_2 = 2$.

Furthermore, you can continue and obtain a homogeneous relation of third order (hint: take a look at $a_{n+3}-3a_{n+2}+3a_{n+1}-a_n$; as bonus, you can make a hypothesis why we take binomial coefficients here), which, given correct initial values, would produce the necessary sequence.

Recursive definitions - cannot figure this one out

1 Answers1