Results 1 to 2 of 2

Thread: setup an induction

  1. #1
    Junior Member
    Oct 2008

    setup an induction


    Could someone help me with setting up a problem . So i want to prove something by induction on k = 0,1,2,3,4...n, clearly $\displaystyle k \in Z+ $

    I have two functions: g(x) and f(x) and i have observed that

    $\displaystyle g(0) = y $
    $\displaystyle f(0) = g(0) = y $
    $\displaystyle f(1) = g(f(0))+g(g(f(0))) $
    $\displaystyle f(2) = g(f(1))+g(g(f(1)))$
    $\displaystyle ...$
    so it looks like :
    $\displaystyle f(k) = g(f(k-1))+g(g(f(k-1)))$ and if i check that for all k up to 100 i get correct numbers.

    And as I said i would like to prove this ($\displaystyle f(k) = g(f(k-1))+g(g(f(k-1)))$) by induction on k So my question is what is my base case and what my induction hypothesis? To me it looks like my base case is :

    $\displaystyle g(0) = y $
    $\displaystyle f(0) = g(0) = y $

    and my induction H:

    $\displaystyle f(k) = g(f(k-1))+g(g(f(k-1)))$

    but what confuses me is if if i plug in 0 for k here i get :

    $\displaystyle f(0) = g(f(0))+g(g(f(0)))$
    $\displaystyle f(0) = g(y)+g(g(y))$

    which is not y which means that either i have wrong idea about my base case (although i always recieve f(0) = g(0)) or my induction hypothesis is wrong (but for all k > 0 i always get the right numbers if i apply $\displaystyle f(k) = g(f(k-1))+g(g(f(k-1)))$ ). I don't know how to connect these two together.

    One more information . This ofcourse works if y = 0 but y = 1,2,3..n so $\displaystyle y\in N$ and $\displaystyle g(y)> y$

    Thank you

    Follow Math Help Forum on Facebook and Google+

  2. #2
    Mar 2013

    Re: setup an induction


    You made a small error in plugging in 0 for k.

    If you were to plug in 0, you would get
    $\displaystyle f(0) = g(f(-1)) + g(g(f(-1)))$
    Now, $\displaystyle f$ probably is not defined on -1, so what you are trying to prove is this:

    1. For $\displaystyle n=0$, $\displaystyle f(0) = g(0) = y$.
    2. For $\displaystyle n=1, 2, 3, ...$, $\displaystyle f(k) = g(f(k-1)) + g(g(f(k-1)))$.

    The second part can be proved by induction, proving the following two subparts seperately:
    2a. $\displaystyle f(1) = g(f(0)) + g(g(f(0))$
    2b. If $\displaystyle f(k) = g(f(k-1))) + g(g(f(k-1)))$ (induction hypothesis), then $\displaystyle f(k+1) = g(f(k))) + g(g(f(k)))$

    Hope this helps
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Reimann Sum Setup
    Posted in the Calculus Forum
    Replies: 1
    Last Post: Nov 30th 2012, 08:17 AM
  2. GLMM setup
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: May 14th 2012, 04:44 AM
  3. Setup help
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: Jul 15th 2009, 09:20 PM
  4. Problem that I don't know how to setup
    Posted in the Calculus Forum
    Replies: 2
    Last Post: Sep 11th 2008, 05:05 AM
  5. [T-89 Ti]Help! How to setup 5th square of 25?
    Posted in the Calculators Forum
    Replies: 3
    Last Post: Apr 5th 2008, 07:41 AM

Search Tags

/mathhelpforum @mathhelpforum