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.
  
This is a tough problem that will help you grow mathematically. 
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