Date: Wed, 08 Oct 2003 15:58:36 -0500 (CDT) From: Mark Jacobson To: 810-080-01@uni.edu, 810-080-03@uni.edu Subject: Proof for HW problem #6... TEST FRIDAY... URL: http://www.cns.uni.edu/~jacobson/c080.html 5n(n + 1) Prove that 5 + 10 + 15 + ... + 5n = ---------------- 2 ---------------------------------------------------------------- Before I prove this, let us look at how the formula was derived: ---------------------------------------------------------------- Rewrite it so each term is explicitly showing the formula, and so we show the 3rd to last and 2nd to last terms. Term number 1 2 3 ... n-2 n-1 n <--- n terms ------- 5(1) + 5(2) + 5(3) + ... + 5(n-2) + 5(n-1) + 5(n) = 5 + 10 + 15 + ... + 5n-10 + 5n-5 + 5n = 5 + 5n = 5n + 5 pair 1st and last terms 10 + 5n-5 = 5n + 5 pair 2nd and 2nd to last terms 15 + 5n-10 = 5n + 5 pair 3rd and 3rd to last terms n It we have n terms and we pair them up, we now have --- terms. 2 Since each term = 5n + 5 [ or 5(n+1) ], if you wish to factor out 5, ------ ------ we have calculated that the sum of n terms is: n(5n+5) 5n(n + 1) ------- = --------- 2 2 What would be the 4th to last term in the series of n terms that is being summed. Easy: 5(n - 3) is the 4th to last term 5n-15 5(n - 2) is the 3rd to last term 5n-10 5(n - 1) is the 2nd to last term 5n-5 5n is the LAST TERM. 5n 5(n - 4) or 5n - 20 is the 5th to last term. -------- ------- What would the 4th term be? 5(4) = 20 4th term 5(3) = 15 3rd term 5(2) = 10 2nd term 5(1) = 5 1st term TERM 1 2 3 4 n-4 n-3 n-2 n-1 n - -- -- -- ----- ----- ----- ---- -- Prove 5 + 10 + 15 + 20 + ... + (5n-20) + (5n-15) + (5n-10) + (5n-5) + 5n = n(5n+5) ------- 2 for all n >= 1. Inductive Proof of page 105 Exercise #6 from section 2.2 of Gersting: BASIS STEP: n = 1 5(1) = 5 and 5(1)(1 + 1) 5(2) 10 ----------- = ------- = ----- = 5 SHOWN! PROVEN. 2 2 2 LHS = RHS 1 1 5 = 5 Inductive Step: I. Assume as the IH (INDUCTIVE HYPOTHESIS) that P(k) is TRUE, for n = k, where k is some arbitrary integer >= 1. 5k(k+1) Assume as IH that 5 + 10 + ... + 5k = --------- for some k >= 1. 2 II. Must try to show that P(k+1) is TRUE. Need to prove P(k+1). GOAL is to establish that P(k+1) is true. ----- 5(k+1)((k+1) + 1) Need to prove that 5 + 10 + ... + 5(k+1) = ------------------ 2 5(k+1)(k+2) = ------------- 2 III. Do the proof: 5 + 10 + ... + 5(k+1) = 5 + 10 + ... + 5k + 5(k+1) by rewriting the LHS (Left Hand Side) of P(k+1) to show the 2nd to last term. 5 + 10 + ... + 5k + 5(k+1) = 5k(k+1) ------- + 5(k+1) by the INDUCTIVE HYPOTHESIS, by IH 2 -------------------- Please look up in section I for the IH, which is a hyp. --- -------------------------------------------------------------------- Side note: if k+1 = 1001, for example, using the IH substitution means we have just replaced 1,000 terms with 1 term. We have just gotten rid of 999 additions, in return for one multiplication, one addition, and one division. -------------------------------------------------------------------- Now that we have used the IH and made the subtitution of the RHS for the place where we saw and recognized the LHS k k all the rest is careful algebra to show that what we have is none other that the RHS k+1 and since we started with the LHS this chain of equalities will have k+1 proven that LHS = RHS and will have proved P(k+1), which is the GOAL k+1 k+1 ---- -------------------------------------------------------------------- ONE 5 + 10 + ... + 5(k+1) = 5 + 10 + ... + 5k + 5(k+1) by rewriting the LHS (Left Hand Side) of P(k+1) to show the 2nd to last term. TWO 5 + 10 + ... + 5k + 5(k+1) = 5k(k+1) ------- + 5(k+1) by the INDUCTIVE HYPOTHESIS, by IH 2 -------------------- THREE 5k(k+1) ------- + 5(k+1) = 2 5k(k+1) 2 ------- + --- 5(k+1) = 2 2 FOUR 5k(k+1) 10(k+1) ------- + --------- = FIVE 2 2 5k(k+1) + 10(k+1) -------------------- = SIX 2 (5k + 10)(k+1) -------------- = 2 SEVEN 5(k+2)(k+1) ----------- = RHS SHOWN, PROVEN, DONE 2 k+1 ----- ------ ---- Note: Steps ONE and TWO allowed us to use the IH. (IH = INDUCTIVE HYPOTHESIS) Steps THREE, FOUR, FIVE, SIX, and SEVEN were just basic algebra. Hope this helps you understand the pattern of inductive proofs better. ---------------------- See you at the exam on Friday, October 10th. Mark