Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Number Theory
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search