# Proof by induction

joshd
Sum from r=1 to n (3r+1) = n/2(3n+5)

Prove true for n=1:
3*1+1=4 | 1/2(3*1+5)=4

Assume true for n=k:
k/2(3k+5)

Prove true for n=(k+1):
k/2(3k+5) + (3(k+1)+1) | 1/2(k+1)(3(k+1)+5)
k/2(3k+5) + (3k+3+1) | 1/2(k+1)(3k+3+5)
k/2(3k+5) + (3k+4) | 1/2(k+1)(3k+8)

now what? I can't see what factors I can take out of either to make them the same... any ideas?

EDIT: nevermind:

1/2(3k^2+5k+2(3k+4) | 1/2(k+1)(3k+8)
1/2(3k^2+11k+8) | 1/2(k+1)(3k+8)
1/2(k+1)(3k+8) | 1/2(k+1)(3k+8)

Same, therefore proved by induction.

:D

Last edited:

Mentor
Sum from r=1 to n (3r+1) = n/2(3n+5)

Prove true for n=1:
3*1+1=4 | 1/2(3*1+5)=4

Assume true for n=k:
k/2(3k+5)

Prove true for n=(k+1):
k/2(3k+5) + (3(k+1)+1) | 1/2(k+1)(3(k+1)+5)
k/2(3k+5) + (3k+3+1) | 1/2(k+1)(3k+3+5)
k/2(3k+5) + (3k+4) | 1/2(k+1)(3k+8)

now what? I can't see what factors I can take out of either to make them the same... any ideas?

EDIT: nevermind:

1/2(3k^2+5k+2(3k+4) | 1/2(k+1)(3k+8)
1/2(3k^2+11k+8) | 1/2(k+1)(3k+8)
1/2(k+1)(3k+8) | 1/2(k+1)(3k+8)

Same, therefore proved by induction.

:D
An easier way is to break up the summation like this:
$$\sum_{r = 1}^n (3r + 1) = \sum_{r = 1}^n 3r + \sum_{r = 1}^n 1$$
$$=3\sum_{r = 1}^n r + \sum_{r = 1}^n 1$$
You could then show, by induction, that ##\sum_{r = 1}^n r = \frac {n(n + 1)} 2## and that ##\sum_{r = 1}^n 1 = n##, and use these to complete your proof.