Proof by induction

  • Thread starter joshd
  • Start date
  • #1
joshd
26
0
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:

Answers and Replies

  • #2
36,310
8,281
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.
 

Suggested for: Proof by induction

Replies
10
Views
492
Replies
5
Views
595
  • Last Post
Replies
8
Views
100
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
7
Views
206
  • Last Post
Replies
11
Views
414
Replies
5
Views
1K
  • Last Post
Replies
11
Views
620
Top