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
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.