# setup an induction

Printable View

• Mar 29th 2013, 01:53 AM
baxy77bax
setup an induction
Hi,

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 $k \in Z+$

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

$g(0) = y$
$f(0) = g(0) = y$
$f(1) = g(f(0))+g(g(f(0)))$
$f(2) = g(f(1))+g(g(f(1)))$
$...$
so it looks like :
$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 ( $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 :

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

and my induction H:

$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 :

$f(0) = g(f(0))+g(g(f(0)))$
$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 $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 $y\in N$ and $g(y)> y$

Thank you

baxy
• Apr 1st 2013, 01:20 PM
Selinde
Re: setup an induction
Hi,

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

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

1. For $n=0$, $f(0) = g(0) = y$.
2. For $n=1, 2, 3, ...$, $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. $f(1) = g(f(0)) + g(g(f(0))$
2b. If $f(k) = g(f(k-1))) + g(g(f(k-1)))$ (induction hypothesis), then $f(k+1) = g(f(k))) + g(g(f(k)))$

Hope this helps :)