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

### Proof by Induction

```
Date: 4/3/96 at 21:10:35
From: Anonymous
Subject: Mathematical Induction

I was given a proof by my math teacher by the means of
mathemetical induction.

Prove i(nCi) = n2^n-1

I was able to make it true for 1, but when it came time to
assume n=k and K=K+1 I got stuck.  I came down to this
conclusion so far:

L.S = (k+1)+2(k+1C2)+3(k+1C3)+...
```

```
Date: 6/3/96 at 11:27:30
From: Doctor Mike
Subject: Re: Mathematical Induction

Hello Sylvestr@fox.nstn.ca ,

I think the formula your teacher gave is

SUM i*(nCi) = n*2^(n-1)

where the nCi are the famous numbers (called "n Choose i" or
"binomial coefficient") in the n-th row down from the top of
Pascal's Triangle :

1        <-- adds up to 1 = 2^0
1   1       <-- adds up to 2 = 2^1
1   2   1      <-- adds up to 4 = 2^2
1   3   3   1     <-- adds up to 8 = 2^3
1   4   6   4   1    <-- adds up to 16 = 2^4
1   5  10   10  5   1   <-- adds up to 32 = 2^5
etc.

There is a simpler formula  SUM nCi = 2^n  that you should
probably do first.  The key to the induction step on this one is
the same as the next-row-rule for Pascal's Triangle, namely,
(n+1)Ci = nCi + nC(i-1).  Prove this rule without mathematical
induction.  For the triangle, the rule says that a number in the
next row is the sum of the 2 numbers right next to it in the row
above.  Here is how the induction step goes for the simpler
formula.  I'm writing it down in a way that shows the limits of
"i", which you should watch VERY closely.  View this with a font
like Courier (all characters, including blank, have same width).

n+1                  n                   n
SUM (n+1)Ci  =  2 + SUM (n+1)Ci  =  2 + SUM [nCi + nC(i-1)]
i=0                 i=1                 i=1

n           n                   n          n-1
=  2 + SUM nCi  +  SUM nC(i-1)  =  2 + SUM nCi  +  SUM nCi
i=1         i=1                 i=1         i=0

n           n           n    n       n+1
=  SUM nCi  +  SUM nCi  =  2  + 2    =  2
i=0         i=0

Once you know the simpler formula, you can prove the other one.
That induction step also uses the next-row-rule for Pascal's
Triangle, and it starts like this.

n+1                        n
SUM i*(n+1)Ci  =  (n+1) + SUM i*(n+1)Ci
i=1                       i=1

n
=  (n+1) + SUM i*[nCi + nC(i-1)]
i=1

n             n
=  (n+1) + SUM i*nCi  +  SUM i*nC(i-1)
i=1           i=1

n-1     n
=  (n+1) + n*2    +  SUM [(i-1)*nC(i-1) + 1*nC(i-1)]
i=1

n-1     n                   n
=  (n+1) + n*2    +  SUM (i-1)*nC(i-1) + SUM nC(i-1)  =...
i=2                 i=1

and it continues similarly to the end of the other proof.
I hope this helps.

-Doctor Mike,  The Math Forum

```
Associated Topics:
High School Discrete Mathematics
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