# Math Induction?

I've gotten to the "inductive step" but I've had a hard time using algebra to show that k is equal to k+1 Relevance
• You are not trying to show that k is equal to k+1.

Having shown that it is true for some value (n=1 I'm guessing), you are now assuming it is true for n=k and wanting to prove it is true for n=k+1.

Sₙ = ⅓(1 - 1/(3n+1))

Sₙ₌ₖ = 1/(1•4) + 1/(4•7) + 1/(7•10) + ... + 1/((3k-2)(3k+1))

Sₙ₌ₖ = ⅓(1 - 1/(3(k+1)))

Sₙ₌ₖ = k/(3k+1)

Sₙ₌ₖ₊₁ = 1/(1•4) + 1/(4•7) + 1/(7•10) + ... + 1/((3k-2)(3k+1)) + 1/((3(k+1)-2)(3(k+1)+1))

Sₙ₌ₖ₊₁ = Sₙ₌ₖ + 1/((3(k+1)-2)(3(k+1)+1))

Sₙ₌ₖ₊₁ = k/(3k+1) + 1/((3k+1)(3k+4))

Sₙ₌ₖ₊₁ = (k(3k+4) + 1)/((3k+1)(3k+4))

Sₙ₌ₖ₊₁ = (3k² + 4k + 1)/((3k+1)(3k+4))

Sₙ₌ₖ₊₁ = (3k+1)(k+1)/((3k+1)(3k+4)) then k≠-1/3 (as we are dealling with integers) so

Sₙ₌ₖ₊₁ = (k+1)/(3k+4)

Sₙ₌ₖ₊₁ = ⅓(3k+3)/(3k+4)

Sₙ₌ₖ₊₁ = ⅓((3k+4 - 1)/(3k+4))

Sₙ₌ₖ₊₁ = ⅓(1 - 1/(3k+4))

Sₙ₌ₖ₊₁ = ⅓(1 - 1/(3(k+1)+1))

Sₙ = ⅓(1 - 1/(3n+1))

Sₙ = ⅓(1 - 1/(3n+1)) is true for all integers n greater than or equal to the value you originally proved to be true.

• First, let's rewrite the formula for S_n in more convenient form

S_n = (1/3)*(1-1/(3n+1))= n/(3n+1)

This is the sum of sequence where last, n-th, term is

A_n = 1/((3n-2)(3n+1))

To prove formula for S_n we need to make two steps

1) The initial or base case: prove that the statement holds for 0, or 1.

2) The induction step, inductive step, or step case: find S_n+1 and show that its formula is same as for S_n but with n+1 instead of n

1) Base case n=1

S_1=1/(3*1+1)=1/4   .... correct

2) induction step

(n+1)th term is

A_n+1= 1/((3(n+1)-2)(3(n+1)+1)) =1/((3n+1)(3n+4))

S_n+1 = S_n + A_n+1

= n/(3n+1) + 1/((3n+1)(3n+4))

= n(3n+4)/((3n+1)(3n+4)) + 1/((3n+1)(3n+4))

= (n(3n+4)+1) / ((3n+1)(3n+4))

= ((3n+1)(n+1)) / ((3n+1)(3n+4))

= (n+1) / (3n+4)

= (n+1) / (3(n+1)+1)

Compare this to formula for S_n. They're the same except that n is replaced with n+1

Our proof is complete.

• (1/3) ( 1 - 1 / (3 n + 1)) + 1 / [ (3n+1)(3n+3) ]  =

[ n / (3n + 1)] + 1/ [ (3n+1)(3n+ 4) ] =

[ 3n² + 4 n + 1] / [ (3n+1)(3n+4) ] = ( n + 1) / [ 3(n+1) + 1] ≡

(1/3) ( 1 - 1/(3n+4) )

• Let's see where the algebra goes.  Let A_n be the nth term in the sum, so that:

A_n = 1/[(3n - 2)(3n + 1)]

S_n = A_1 + A_2 + ... + A_n

S_(n+1) = S_n + A_(n+1)

It shouldn't be hard to see that A_(n+1) = 1/[(3n + 1)(3n + 4)].

If the formula given is valid for S_n then you can use it to replace S_n:

S_(n+1) = S_n + 1/[(3n + 1)* (3n + 4)]

= (1/3)[1 - 1/(3n + 1)] + 1/[(3n + 1)(3n + 4)]

= (1/3) - 1/[3(3n + 1)] + 1/[(3n + 1)(3n + 4)]

Convert the last two terms to a have a common denominator of 3(3n+1)(3n+4).  Multiply the 2nd fraction by (3n+4)/(3n+4) and the final one by 3/3 to get

S_(n+1) = (1/3) - (3n+4)/[3(3n + 1)(3n + 4)] + 3/[3(3n + 1)(3n + 4)]

= (1/3) + (-3n - 4 + 3) / [3(3n + 1)(3n + 4)]

= (1/3)  + (-3n - 1) / [3(3n + 1)(3n + 4)]

= (1/3) - 1 / [3(3n + 4)]   .... after canceling (-3n - 1)/(3n + 1) = -1

= (1/3)[1 - 1/(3n + 4)]

...and since 3n + 4 is the same as 3(n+1) + 1, you have the same formula for S_(n+1) and it's valid whenver the formula for S_n was.