• Support PF! Buy your school textbooks, materials and every day products Here!

Proof by induction

  • #1

Homework Statement



[tex] \sum_{i=1}^{n} (i \prod_{j=1}^{i}_{j}) = \prod_{i=1}^{n+1}_{i} - 1 [/tex]

Homework Equations





The Attempt at a Solution



First show the base case. That easys just shows it holds for n=1. Not sure where to go from there? What term do I add to both sides? Not really sure what the i means in front of the [tex]\prod [/tex] on the left side
 

Answers and Replies

  • #2
radou
Homework Helper
3,115
6
Assume it holds for some k. Now try to evaluate for k + 1 and use the fact that it holds for k.
 
  • #3
Assume it holds for some k. Now try to evaluate for k + 1 and use the fact that it holds for k.
Yes. This requires that I need to add some term to both sides. Not really sure what term I need to use to construct the induction for k+1
 
  • #4
radou
Homework Helper
3,115
6
You have and equality which you wish to show holds for k + 1. Evaluate the left side for k + 1 first - try to express this as a sum of two terms one of which equals the sum for k (which you assumed holds).
 
  • #5
You have and equality which you wish to show holds for k + 1. Evaluate the left side for k + 1 first - try to express this as a sum of two terms one of which equals the sum for k (which you assumed holds).
Can you give an example?
 
  • #6
radou
Homework Helper
3,115
6
OK, here's how you should start:

[tex]
\sum_{i=1}^{k+1} (i \prod_{j=1}^{i}_{j}) = \sum_{i=1}^{k} (i \prod_{j=1}^{i}_{j}) + (k+1) \prod_{j=1}^{k+1}_{j}
[/tex]
 
  • #7
Ok so first I replaced all the sum stuff with the right hand side to make it easier to read. By substituting the right side of left side of the initial equality with the right side. That should work fine right?

The I have:

[tex]
\prod_{j=1}^{k+1}_{j} - 1 = \prod_{j=1}^{k+1}_{j} - 1 + (k+1) \prod_{j=1}^{k+1}_{j}
[/tex]

But it doesn't seem right..
 
  • #8
radou
Homework Helper
3,115
6
Why wouldn't it seem right? You only need to factor out [tex]\prod_{j=1}^{k+1}_{j}[/tex].
 
  • #9
[tex]
\prod_{j=1}^{k+1}_{j} - 1 = \prod_{j=1}^{k+1}_{j} - 1 + (k+1) \prod_{j=1}^{k+1}_{j}
[/tex]


Ok so I also cancel out the -1 on both sides, then I factor out
[tex]\prod_{j=1}^{k+1}_{j}[/tex] and I get

[tex]\prod_{j=1}^{k+1}_{j} = 1 +(k+1)(\prod_{j=1}^{k+1}_{j})[/tex]

then cancel out the prod_{j=1}^{k+1}_{j} ?

[tex]
1 = 1 + (k+1)
[/tex]

[tex]
k=-1
[/tex]

What now?
 
  • #10
radou
Homework Helper
3,115
6
You should start thinking about what you're doing. Let's start all over:

[tex]
\sum_{i=1}^{k+1} (i \prod_{j=1}^{i}_{j}) = \sum_{i=1}^{k} (i \prod_{j=1}^{i}_{j}) + (k+1) \prod_{j=1}^{k+1}_{j} = \prod_{j=1}^{k+1}_{j} - 1 + (k+1) \prod_{j=1}^{k+1}_{j}
[/tex]

You are not canceling out different sides of the equation, you're only evaluating an equality - now factor out [tex]
\prod_{j=1}^{k+1}_{j}
[/tex].
 

Related Threads for: Proof by induction

  • Last Post
Replies
6
Views
725
  • Last Post
Replies
2
Views
881
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
10
Views
1K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
2
Views
592
  • Last Post
Replies
4
Views
3K
Top