Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | Next revision Both sides next revision | ||
|
sav08:proof_of_first_lecture01_example [2008/02/19 14:15] vkuncak |
sav08:proof_of_first_lecture01_example [2008/02/19 14:16] vkuncak |
||
|---|---|---|---|
| Line 33: | Line 33: | ||
| * **Inductive hypothesis.** Assume that the claim holds for all values less than $y$. | * **Inductive hypothesis.** Assume that the claim holds for all values less than $y$. | ||
| * Goal: show that it holds for $y$ where $y > 0$. | * Goal: show that it holds for $y$ where $y > 0$. | ||
| - | * **Case 1**: $y = 2k$. Note $k < y$. By definition | + | * **Case 1**: $y = 2k$. Note $k < y$. By definition and I.H. |
| \[ | \[ | ||
| f(x,y) = f(x,2k) = 2 f(x,k) = 2 (x k) = x (2 k) = x y | f(x,y) = f(x,2k) = 2 f(x,k) = 2 (x k) = x (2 k) = x y | ||
| \] | \] | ||
| * | * | ||
| - | * **Case 2**: $y = 2k+1$. Note $k < y$. By definition | + | * **Case 2**: $y = 2k+1$. Note $y-1 < y$ and $k < y$. By definition and I.H. |
| \[ | \[ | ||
| f(x,y) = f(x,2k+1) = x + f(x,2k) = x + 2 f(x,k) = x + 2 (x k) = x (2 k + 1) = x y | f(x,y) = f(x,2k+1) = x + f(x,2k) = x + 2 f(x,k) = x + 2 (x k) = x (2 k + 1) = x y | ||