Series Proofs by Induction (+notes)

Steps

• 1. Assume the statement is true for any particular value, so take n=k (write this down)
• 2. Use the assumption to show that the statement is also true for n=k+1
• 3. Show that the statement is true for the first value, usually n=1
• 4. Conclude the proof; "as the statement is true for n=1, and if true for n=k is also true for n=k+1 we have proved by induction that is true for n≥1"

Example 1

• Prove by induction that (n)Σ(r=1) r^3 = (n^2(n+1)^2)/4
• Assume that n=k : (k)Σ(r=1) r^3 = (k^2(k+1)^2)/4
• Show that when n=k+1 : (k+1)Σ(r=1) r^3 = ((k+1)^2(k+2)^2)/4
• Now we can say : (k+1)Σ(r=1) r^3 = (k)Σ(r=1) r^3 + (k+1)^3 ( (k+1)^3 is the kth term , and we find it by replacing r with k+1 in the sums rule)
• This also equals: (k^2(k+1)^2)/4 + (k+1)^3 (as (k)Σ(r=1) r^3 = (k^2(k+1)^2)/4) , which cancels to 1/4(k+1)^2(k^2+4k+4) , and this quadratic can be factorised to (k+2)(k+2) , so we can say: ((k+1)^2(k+2)^2)/4 as required , NOTE: this "as required" is very important
• Show that it's true for n=1 : LHS ; (1)Σ(r=1)r^3 = 1^3 = 1 RHS; (1^2(1+1)^2)/4 = 1 therefore it's true when n=1
• Since (n)Σ(r=1) r^3 = (n^2(n+1)^2)/4 for n=1, and if true for n=k => n=k+1, we have proved that by induction that (n)Σ(r=1) r^3 = (n^2(n+1)^2)/4 for n≥1
• (note that this should be copied exactly with all the words and everything)

Example 2

• Prove by induction that (n)Σ(r=1) r(r+2) = (n(n+1)(n+7))/6 for all positive integers
• Assume true for n=k ; (k)Σ(r=1) r(r+2) = (k(k+1)(k+7))/6
• Show that true for n=k+1 ; (k+1)Σ(r=1) r(r+2) = ((k+1)(k+1)(2k+9))/6
• (k+1)Σ(r=1) r(r+2) = (k)Σ(r=1) r(r+2) + (k+1)(k+3) ( (k+1)(k+3) used as we replace r from sums rule with (k+1)
• This also equals: (k(k+1)(2k+7) + (k+1)(k+3) , which factorises as follows: (k+1)[(k(2k+7)/6 + (k+3)] , 1/6 (k+1)[k(2k+7)+6k+18] , 1/6 (k+1)[2k^2+13k+18] , 1/6(k+1)(k+2)(2k+9) which = ((k+1)(k+2)(2k+9))/6 as required.
• Show true for n=1 : LHS ; 1(1+2) = 3 RHS ; (1(1+1)(2+7))/6 = 18/6 = 3 therefore true for n=1
• Since true for n=1, and n=k => n=k+1 proven by induction for all n∈Z ≥ 1 that (n)Σ(r=1) r(r+2) = (n(n+1)(n+7))/6 .

Notes

• To find the kth terms, we replace r in the sums rule with k+1 and add this to n=k.
• Make sure to remember to say "as required"
• The wording of these is very important too.