0

$$f(0) = 1\\ h(0) = 1\\ g(0) = 0\\ f(n + 1) = 1 − h(n)\\ h(n + 1) = 1 − g(n + 1)\\ g(n + 1) = f(n) $$

Prove using induction that $∀n ∈ \Bbb N: f(n) + g(n) = 1$

what i've done so far:

Base Case: $n=0$ $$ f(0) + g(0) = 1\\ 1 + 0 = 1\\ 1 = 1 $$

Step Case: $$ f(n+1) + g(n+1) = 1\\ 1 - h(n) + f(n) = 1\\ 1 - h(0) + f(0) = 1\\ 1 - 1 + 1 = 1\\ 1 = 1 $$ Is this the right way to do it?

M.G
  • 3,709
Paul
  • 31
  • You should use Latex to format your mathematics – John Martin Apr 14 '16 at 16:31
  • You should prove from left hand side $f(n+1) + g(n+1)$ to right hand side $1$ in both the base and step cases. – peterwhy Apr 14 '16 at 16:31
  • how ? @peterwhy – Paul Apr 14 '16 at 16:33
  • Going off of what peterwhy said, you assume that the result holds for all integers up to $n$, and then show that it does for $n+1$; it looks like you assumed that it is holding for $n+1$. I will post an answer with some details – John Martin Apr 14 '16 at 16:34
  • Instead of saying $f(0) + g(0) = 1$ on the first line without giving any reason, you should say like $$LHS = f(0) + g(0) = 1 + 0 = 1 = RHS$$And it is not clear where you have used your inductive hypothesis $$f(n) + g(n) = 1$$ – peterwhy Apr 14 '16 at 16:34

1 Answers1

0

Once you have done the base case, let's look at the induction step. Assume that $f(k) + g(k) = 1$ for all $k\leq n$. Then we have \begin{align*} f(n+1) + g(n+1) &= 1 - h(n) + f(n)\\ &= 1 - (1- g(n)) + f(n)\\ &= g(n) + f(n) \\ &= 1 \end{align*} Because $f(n) + g(n) = 1$ by assumption.

John Martin
  • 1,229
  • 8
  • 17
  • how did you get 1 - (1-g(n)) + f(n) ? – Paul Apr 14 '16 at 16:48
  • and why 1 - h(n) + f(n) ? – Paul Apr 14 '16 at 16:49
  • Well we know that $h(n+1) = 1 - g(n+1)$ for all $n$, so $h(n) = 1 - g(n)$. Moreover we know that $f(n+1) = 1 - h(n)$ - these are coming from the list of properties that you wrote in your initial question. – John Martin Apr 14 '16 at 16:53
  • okay now i get it, but i don't understand how u get 1-(1-g(n)) to g(n) ? – Paul Apr 14 '16 at 16:58
  • @clabbe $$1-(1-g(n)) = 1-1+g(n) = g(n)$$ – peterwhy Apr 14 '16 at 16:59
  • This is just arithmetic: $1 - (1 - g(n)) = 1 - 1 + g(n)$ (just distribute the negative through the parentheses...) – John Martin Apr 14 '16 at 16:59
  • yes yes got it now! – Paul Apr 14 '16 at 16:59
  • okay so is that enough for the problem? is it complete now? – Paul Apr 14 '16 at 17:01
  • Yes. Induction always works the same way: You first show the base step and then you show the induction step. You have then concluded that whatever it is that you are proving holds for all integers. Which we have just done here! – John Martin Apr 14 '16 at 17:02
  • okay thank u so much! – Paul Apr 14 '16 at 17:04
  • You're welcome. Also, I notice that you are pretty new here; you can vote for questions and answers that you like. And you can accept an answer by clicking on the check mark next to it. This shows other people browsing SE that the question has been answered. – John Martin Apr 14 '16 at 17:06