64 choices

Number Theory Level 2

$a_n = \dbinom{n}{a_{n-1}}$ for $n>1$ , and $a_1 = 1$ .

What is $a_{64}$ ?

Clarification: The notation $\binom{x}{y}$ indicates "x choose y" or the binomial coefficient indexed by x and y.

Image credit: http://www.fluenceportland.com/

2 solutions

Chew-Seong Cheong
Apr 23, 2016

We claim that $a_n = n$ for all $n$ and then prove it by induction.

For $n=1$ , $\implies a_1 = 1$ as given. Therefore, the claim is true for $n=1$ .
Assume that $a_n = n$ is true for $n$ , then: $a_{n+1} = \begin{pmatrix} n+1 \\ a_n \end{pmatrix} = \begin{pmatrix} n+1 \\ n \end{pmatrix} = n + 1$

The claim is also true for $n+1$ , therefore it is true for all $n$ .

Therefore, $a_{64} = \boxed{64}$ .

Little typo in 2 step: at the final is n+1.

Mateo Matijasevick - 5 years, 1 month ago

Thanks a lot. I have edited it.

Chew-Seong Cheong - 5 years, 1 month ago

Nice solution, Chew-Seong! :)

Geoff Pilling - 5 years, 1 month ago

Geoff Pilling
Apr 23, 2016

$a_1 = 1, a_2 = \binom{2}{1}, a_3 = \binom{3}{2}$ , etc. So, $a_{64} = \binom{64}{63} = \boxed{64}$ .