Proof by Induction: Solving Homework Involving Prods & Sums

[yankees26an]

Homework Statement

$$\sum_{i=1}^{n} (i \prod_{j=1}^{i}_{j}) = \prod_{i=1}^{n+1}_{i} - 1$$

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 $$\prod$$ on the left side

 

[radou]

Assume it holds for some k. Now try to evaluate for k + 1 and use the fact that it holds for k.

 

[yankees26an]

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

 

[radou]

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).

 

[yankees26an]

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?

 

[radou]

OK, here's how you should start:

$$\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}$$

 

[yankees26an]

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:

$$\prod_{j=1}^{k+1}_{j} - 1 = \prod_{j=1}^{k+1}_{j} - 1 + (k+1) \prod_{j=1}^{k+1}_{j}$$

But it doesn't seem right..

 

[radou]

Why wouldn't it seem right? You only need to factor out $$\prod_{j=1}^{k+1}_{j}$$.

 

[yankees26an]

$$\prod_{j=1}^{k+1}_{j} - 1 = \prod_{j=1}^{k+1}_{j} - 1 + (k+1) \prod_{j=1}^{k+1}_{j}$$


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

$$\prod_{j=1}^{k+1}_{j} = 1 +(k+1)(\prod_{j=1}^{k+1}_{j})$$

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

$$1 = 1 + (k+1)$$

$$k=-1$$

What now?

 

[radou]

You should start thinking about what you're doing. Let's start all over:

$$\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}$$

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