Proof by Induction: Solving Homework Involving Prods & Sums

In summary, the homework equation holds for some k. After evaluating for k + 1, it is found that the equation holds for k - 1.
  • #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
 
Physics news on Phys.org
  • #2
Assume it holds for some k. Now try to evaluate for k + 1 and use the fact that it holds for k.
 
  • #3
radou said:
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
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
radou said:
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
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
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
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].
 

1. What is proof by induction?

Proof by induction is a mathematical technique used to prove that a statement is true for all positive integers. It involves three steps: the base case, the inductive hypothesis, and the inductive step.

2. How do you use proof by induction to solve homework problems involving products and sums?

To use proof by induction to solve homework problems involving products and sums, you first need to identify the statement you are trying to prove. Then, you need to show that the statement is true for the smallest possible value (the base case). After that, you assume that the statement is true for some arbitrary value (the inductive hypothesis) and use that assumption to prove that it is also true for the next value (the inductive step). Finally, you use the inductive hypothesis and the inductive step to prove that the statement is true for all positive integers.

3. What is the base case in proof by induction?

The base case is the first value for which you prove the statement to be true. It is typically the smallest possible value (usually 0 or 1) for which the statement can be easily proven to be true.

4. How do you determine the inductive hypothesis in proof by induction?

The inductive hypothesis is an assumption that the statement is true for some arbitrary value. It is usually written as P(k), where k is the arbitrary value. To determine the inductive hypothesis, you need to look at the statement and figure out what value would make it true for all positive integers.

5. What is the inductive step in proof by induction?

The inductive step is the step in which you use the inductive hypothesis to prove that the statement is also true for the next value. This step is crucial in completing the proof and showing that the statement is true for all positive integers.

Suggested for: Proof by Induction: Solving Homework Involving Prods & Sums

Replies
6
Views
697
Replies
15
Views
893
Replies
4
Views
718
Replies
6
Views
934
Replies
7
Views
895
Replies
4
Views
945
Back
Top