# Proof by Induction: Explaining Step 3 to 4 | Math Homework

• Robb

## Homework Statement

Attached are notes from class. Can someone please explain what happens to (-x(n+1)) in step 3 to step 4. Not sure why it goes away. Thanks!

## The Attempt at a Solution

#### Attachments

• inductive.pdf
198.9 KB · Views: 140

## Homework Statement

Attached are notes from class. Can someone please explain what happens to (-x(n+1)) in step 3 to step 4. Not sure why it goes away. Thanks!

## The Attempt at a Solution

Your notes (did you take them?) aren't very helpful, as there is a relatively minor error in them -- a misplaced parenthesis.
Here's the corrected version of step 2.
##\Pi_{i = 1}^{n + 1} (1 - x_i) \ge \left(1 - \sum_{i =1}^n x_i)\right)(1 - x_{n + 1})##
The right side of your inequality is incorrect, due to the parentheses being in the wrong place. One of the factors in the inequality is ##(1 - \sum_{i = 1}^n x_i)## and the other is ##(1 - x_{n + 1})##

The error is corrected in step 3. Now, to answer your question, what do ##-\sum_{i = 1}^n x_i## and ##-x_{n + 1}## combine to make?

Last edited:
the only things I'd add are

i.) if OP has proven Union Bound (Boole's Inequality), this result follows almost immediately -- though you need to think carefully about sets and coin tossing to get the result.

- - - -
edit: geometric mean idea ran into too much trouble. Boole's Inequality still gives a very quick and satisfying answer.

Last edited: