Recognize the series?

Number Theory Level pending
  • A m 0 = 1 A_{m0} =1 \forall m 0 m \ge 0
  • A 0 n = 0 A_{0n} = 0 for n > 0 n>0
  • A m n = A m 1 , n + A m 1 , n 1 A_{mn}=A_{m-1,n} + A_{m-1,n-1} for m > 0 m>0 and n > 0 n>0

A m n A_{mn} is defined as above, evaluate A 15 , 7 A_{15,7} .


The answer is 6435.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Chew-Seong Cheong
Aug 31, 2016

We can prove the claim that A m n = ( m n ) A_{mn} = {m \choose n} is true for all m , n 0 m, n \ge 0 by induction.

  1. For m = n = 0 m=n=0 , A 00 = ( 0 0 ) = 1 A_{00} = {0 \choose 0} = 1 as defined in A m 0 m 0 A_{m0} \ \forall \ m \ge 0 . Therefore, the claim is true for m = n = 0 m=n=0 .

  2. For m = 0 m=0 and n > 0 n>0 , A 00 = ( 0 n ) = 0 A_{00} = {0 \choose n} = 0 as defined in A 0 n = 0 A_{0n} = 0 for n > 0 n>0 . Therefore, the claim is true for m = 0 m=0 and n > 0 n>0 .

  3. Note that steps 1 and 2 prove that the claim is true for m = 0 m=0 for all n 0 n \ge 0 . Now, assuming the claim A m n = ( m n ) A_{mn} = {m \choose n} is true for m m , then:

A m + 1 , n + 1 = A m , n + 1 + A m , n = ( m n + 1 ) + ( m n ) By Pascal’s identity: ( n k ) + ( n k 1 ) = ( n + 1 k ) = ( m + 1 n + 1 ) \begin{aligned} \quad A_{\color{#3D99F6}{m+1,n+1}} & = A_{m,n+1} + A_{m,n} \\ & = {m \choose n+1} + {m \choose n} & \small \color{#3D99F6}{\text{By Pascal's identity: }{n \choose k} + {n \choose k-1} = {n+1 \choose k}} \\ & = {\color{#3D99F6}{m+1} \choose \color{#3D99F6}{n+1}} \end{aligned} t

\quad Therefore, the claim is true for m + 1 m+1 and hence true for all m 0 m \ge 0 .

A 15 , 7 = ( 15 7 ) = 6435 \implies A_{15,7} = {15 \choose 7} = \boxed{6435}

Nice argument, @Chew-Seong Cheong !

Geoff Pilling - 4 years, 9 months ago
Geoff Pilling
Aug 31, 2016

This series is just a fancy way of saying A m n = ( m n ) A_{mn} = \binom{m}{n}

So, A 15 , 7 = ( 15 7 ) = 6435 A_{15,7} = \binom{15}{7} = \boxed{6435}

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...