Google Answers Logo
View Question
 
Q: Data structure and algorithm ( Answered,   0 Comments )
Question  
Subject: Data structure and algorithm
Category: Computers > Algorithms
Asked by: math01-ga
List Price: $5.00
Posted: 16 Jul 2003 08:04 PDT
Expires: 15 Aug 2003 08:04 PDT
Question ID: 231625
Using mathematical induction, show that: 

2 + 4 + 6 + 8 + ... + 2n = n(n + 1)
Answer  
Subject: Re: Data structure and algorithm
Answered By: tox-ga on 16 Jul 2003 09:53 PDT
 
Hi there,



Let P(n) denote a proposition depending on n. For instance: 
P(n): 2+4+6+....+2n = n(n+1) 

for n=1, 2, ... 


To prove that P(n) is true for every integer n, we do the following
steps:
Verify P(1) (basis step) 
Prove that is P(k) is true, then so is P(k+1) (induction step) 
Therefore, one proves P(1), then P(2), then P(3), etc... until
infinity.

For the question you've provided, the proof is as follows: 

.: Basis step (show that P(1) is true)
P(1):       2=1(1+1)
	     =2 

P(1) is verified. 


.: Induction step. (show that if P(k) is true, P(k+1) is also true)

    ->Assume<- P(k) is true.  This means that 

     2+4+6+...+2k = k(k+1) 


Show that P(k+1) is true, that is 

2+4+6+...+2k+2(k+1)=(k+1)(k+2) 

To do this, start with the left side of P(k+1) and then modify to
equivalent statements until we get the right side of P(k+1)

 2+4+6+...+ 2k + 2(k+1) 
= (2+4+6+...+2k)+2(k+1) 
= k(k+1) + 2(k+1)     <- the left side of P(k) was replaced with the
right side (remember the assumption at the start of the induction
step)
= (k+1)(k+2)  <- factored out the common term (k+1)
Thus the induction step is complete.

Therefore, by the principle of mathematical induction, it has been
shown that 2 + 4 + 6 + ... + 2n = n(n+1) whenever n is a positive
integer.


If you need clarification on any part of the answer, please request
clarification.

Best regards,
Tox-ga
Comments  
There are no comments at this time.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy