LARA

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
sav08:proof_of_first_lecture01_example [2008/02/19 14:15]
vkuncak
sav08:proof_of_first_lecture01_example [2008/02/20 14:53]
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 $< y$. By definition+     * **Case 2**: $y = 2k+1$. Note $y-1 < 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 + x \cdot (2k) = x (2 k + 1) = x y
 \] \]
 This completes the proof. This completes the proof.