# Discussion 1A

# Induction

Prove that for all , holds.

## Weak induction steps:

**Base case:**Prove that holds**Inductive hypothesis**: Assume that holds for some value of**Inductive step**: Show that holds under the inductive hypothesis

## Strong induction steps:

**Base case**: Prove that holds**Inductive hypothesis**: Assume that holds for all values of between and**Inductive step**: Show that holds under the inductive hypothesis

## Applications

- Divide and conquer/recursion problems
- Binary search, sorting

- Graphs
- Trees

minor typo on 1b: