Proof by induction

  • Thread starter joshd
  • Start date
  • #1
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
35,057
6,793
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.
 

Related Threads on Proof by induction

  • Last Post
Replies
9
Views
3K
  • Last Post
Replies
8
Views
5K
  • Last Post
Replies
6
Views
3K
  • Last Post
Replies
4
Views
8K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
6
Views
5K
Replies
2
Views
7K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
2
Views
3K
Replies
4
Views
2K
Top