wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Proof by Mathematical Induction
        
(Message started by: daemonturk on Sep 12^th, 2009, 7:51am)

Title: Proof by Mathematical Induction
Post by daemonturk on Sep 12^th, 2009, 7:51am

Use proof by mathematical induction to prove that:

(1+2+3+...+n)^2=1^3+2^3+3^3+...+n^3 for n>=1

Need a speedy response.

Title: Re: Proof by Mathematical Induction
Post by towr on Sep 12^th, 2009, 10:42am

The base case is simple
1² = 1³, so it is true for n=1.

Now assume it is true for n-1, so
(1+2+3+...+n-1)²=1³+2³+3³+...+(n-1)³,
then to prove it holds for n, you have to prove that you can go from this to (1+2+3+...+n)²=1³+2³+3³+...+n³.
If you expand the latter a little, you have
(1+2+3+...+n-1)² + 2 n(1+2+3+..n-1) + n² = 1³+2³+3³+...+(n-1)³ + n³
Therefore, to account for the change from the case of n-1 to n, we need to prove that
n² + 2 * n*(1+2+3+..n-1) = n³

Title: Re: Proof by Mathematical Induction
Post by french_math on Jun 9^th, 2010, 3:17am

This is quite easy :

1+2+...+n-1 = (n-1)*n/2, that you can prove by induction too.