# Homework Help: Proof by induction

1. Mar 1, 2010

### yankees26an

1. The problem statement, all variables and given/known data

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

2. Relevant equations

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

2. Mar 1, 2010

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

3. Mar 1, 2010

### yankees26an

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. Mar 1, 2010

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. Mar 1, 2010

### yankees26an

Can you give an example?

6. Mar 1, 2010

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

7. Mar 1, 2010

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

8. Mar 1, 2010

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

9. Mar 1, 2010

### 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?

10. Mar 2, 2010

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