# A question about a sequence.

I'm preparing for the subject exam in November. This is a question that I thought I had the correct answer to.

Let $\left \{a_n \right \}_{n=1}^\infty$ be defined recursively by $a_1=1$ and $a_{n+1}=\left( \frac{n+2}{n} \right) a_n$ for $n\geq 1$. Then what is $a_{30}$ equal to?

So I had no idea how to approach this, so I sought to find a pattern. I noticed $a_2=\binom{3}{1}$, $a_3=\binom{4}{2}$, $a_4=\binom{5}{3}$, $a_5=\binom{6}{4}$, etc., so naturally I thought that $a_{30}=\binom{31}{29}$. However, I checked the answer in the back of my practice test and it says I'm incorrect! Can someone tell me how to do this problem? Thank you!

-
I get $465$ too but I would have written it as cancelling a lot of terms as $\dfrac{31 \times 30 }{2}$ –  Henry Oct 7 '13 at 23:44

Look at some small ones, and you’ll see what’s happening:

$$a_4=\frac53a_3=\frac53\cdot\frac42a_2=\frac{5\cdot4\cdot3}{3!}=\frac{5\cdot4}2=\binom52\;,$$

and

$$a_5=\frac64a_4=\frac64\cdot\frac53a_3=\frac64\cdot\frac53\cdot\frac42a_2=\frac{6\cdot5\cdot4\cdot3}{4!}=\frac{6\cdot5}2=\binom62\;.$$

Now state and prove the general result. (Note that this is equivalent to your answer; if this is the answer in the key, both it and your answer are correct, since they’re the same answer in different form. If the key has some other answer, it’s probably wrong.)

-
There is not a lot of difference between ${n+1 \choose n-1}$ and ${n+1 \choose 2}$ –  Henry Oct 8 '13 at 0:11
@Henry: Agreed; but not knowing whether the answer key was wrong or simply gave $\binom{n+1}2$, I thought it simplest to offer the alternative, and in a form that didn’t assume any real comfort with manipulations of binomial coefficients. –  Brian M. Scott Oct 8 '13 at 0:17