Induction With Binomial Coefficients

Date: 10/16/2000 at 11:31:44
From: Bill Lee
Subject: Number theory - Summation Notation 

I am in the process of studying number theory, and I was poring over a 
problem regarding summation and multiplicative notation. The problem 
that I was given and can not seem to grasp is this, and I will say I 
truly do not know where to begin.

Prove that:

      n   i+k-1     n+k
     SUM (     ) = (   )
     i=1    k       k+1

where n and k are integers with n >= 0 and k >= 0. 

For me, Dr. Math, here is the really sticky part. The problem goes on 
to say that it is customary to set

      a
     ( ) = 0  for integers a and b if 0 <= a < b. 
      b

Can you help me with this one? Thanks.

Date: 10/16/2000 at 13:42:29
From: Doctor Rob
Subject: Re: Number theory - Summation Notation 

I'm not sure what method of proof you are supposed to use here, but a 
proof by mathematical induction on n is not very hard. The base case 
is n = 0, in which case the sum on the left is the empty sum, or 0, 
and the right-hand side is also 0 by the remark about "customary." For 
n = 1, the left side is 1 and the right side is also 1. Suppose you 
know the stated equation is true for n and all values of k >= 0. Then

     n+1  i+k-1     n   i+k-1     n+1+k-1
     SUM (     ) = SUM (     ) + (       ), by what the notation 
means,
     i=1    k      i=1    k          k   

                    n+k     n+k
                 = (   ) + (   ), by the induction hypothesis,
                    k+1      k 

                    (n+1)+k
                 = (       ), by using the identity for binomial
                      k+1     coefficients from Pascal's triangle.

Thus the equation is also true for n+1 and all values of k >= 0. Then 
apply the Principle of Mathematical Induction to conclude that it is 
true for all values of n >= 0 and all values of k >= 0.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/   

Date: 10/17/2000 at 23:22:00
From: Bill Lee
Subject: Re: Number theory - Summation Notation 

Thank you, Dr. Rob, for responding so quickly to my question. I do 
understand your point of view for this proof, meaning proof by 
induction is one way, but I am still confused on the notation of it 
all. 

In my experience with mathematical induction, I have never seen  
      
      a
     ( ) = 0
      b

used in mathematical induction. I thought that this notation might be 
related to eigenvectors in linear algebra. Is this true or am I in 
left field on this one?

I guess what I am saying is that I see how the induction process could 
be one way to solve this problem, but I am not sure I follow your 
proof of it. Is there a way that you could help me understand this a 
little better? When this problem was presented in class, there was no 
mention of mathematical induction as a way to solve it. I would like 
to know why you chose mathematical induction and how induction fits 
with the notation that is given in the stated problem.

Once again, I appreciate all your help with this. Any light that you 
could shed on this issue would be most appreciated.

Thank you.

Date: 10/20/2000 at 14:01:23
From: Doctor Rob
Subject: Re: Number theory - Summation Notation 

Thanks for writing back.

You wrote:
>... I am still confused on the notation of it all.

Is it the summation notation or the binomial coefficient notation that 
you find confusing?

>In my experience with mathematical induction, I have never seen  
>
>      a
>     ( ) = 0 
>      b
>
>used in mathematical induction. 

Good! That means I have shown you something new, and you have a chance 
to learn from the experience.

>I thought maybe that this notation might be related to eigenvectors 
>in linear algebra. Is this true or am I in left field on this one?

The relation between these ideas is either very remote or nonexistent. 

>When this problem was presented in class, there was no mention of 
>mathematical induction as a way to solve it.

I warned you that this might not be the way that the poser of the 
problem wanted this proved. I would be interested in what method was 
used, if you care to tell it. (I have a sneaking suspicion that 
whatever proof was presented has a hidden induction concealed within.)

>I would like to know why you chose mathematical induction and how 
>induction fits with the notation that is given in the stated problem?

The notation

      n
     SUM a(i)
     i=1

is defined to mean this: consider the sequence a(i) for 1 <= i <= n, 
and add up all those terms of the sequence, or, in symbols,

     a(1) + a(2) + ... + a(n-1) + a(n)

If there is just one term, no adding takes place, and you just have 
a(1). (This is the result of adding up a column of 1 row of numbers 
containing a(1).) If there are no terms, no adding takes place, and 
you just have 0. (This is the result of adding up a column with 0 rows 
of numbers.) The summation notation is used to dispose of those 
annoying dots in the ellipsis "..." above, and to make rigorous the 
phrase "and so on" implied by them.

If you change n to n+1 in the either expression above, what you get is 
a sum with one additional summand, namely a(n+1). That is what 
suggests using induction, that the sum of the first n terms can be 
separated from the (n+1)st term in this way. Then the induction 
hypothesis can be applied to the first part, and somehow the last term 
can be combined with the result of using the hypothesis to prove the 
induction step.

In the proof I gave, I did just that to establish the induction step. 
I assumed the statement was true for some particular value n, and then 
wrote down one side of the equation for the statement corresponding to 
the next value of n, that is, n+1. Then I separated the last term from 
the first n terms and applied the induction hypothesis to the first 
part, getting an expression for the sum of the first n terms as a 
single binomial coefficient. 

Then I combined that binomial coefficient with the one that was the 
last term of the sum. This was easy to do by the rule for Pascal's 
triangle, which states that every number in the triangle is the sum of 
the two above it. The two coefficients we have are adjacent entries on 
the same line of the triangle, so their sum is the one between them on 
the next line of that triangle. That gave us the sum as a single 
binomial coefficient, and that was just what was needed for the 
right-hand side of the equation for the statement corresponding to 
n+1.

I hope this is clearer. If not, write again.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/