0

Determine whether is this a valid recursive definition of a function f from the set of nonnegative integers to the set of integers. If f is well defined (valid recursion), find a formula for f(n) when n is a nonnegative integer and prove your formula is valid.

f(0) = 1, f(n) = -f(n-1) for n >= 1

This is extra work for a final exam tomorrow.

So I got f(0) = -f(0 - 1) = 1, so 1 = 1

So what are the next steps that I do next?

Rich Sanchez
  • 69

1 Answers1

2

First, you should be able to make the (correct) guess that the function is $f(n) = (-1)^n$. Then, you prove this by induction. As you pointed out, the first step is to show the base case, that is that the claim holds for $n=0$. $$ f(0) = (-1)^0 = 1 $$ Next, we suppose that the if claim holds for $n-1$, it must also hold for $n$. This is the induction step. $$ f(n) = -f(n-1) = -1(-1)^{n-1} = (-1)^n $$ By the principle of mathematical induction, $f(n) = (-1)^n$ for $n\geq 0$.

Alec
  • 1,205
  • Ok, so why is the n an exponent now? Looks familiar, but please refresh my memory. Thanks – Rich Sanchez Dec 12 '13 at 06:57
  • This is a guess you are making about the formula. The reasoning behind the guess varies, but you might want to try it out for the first couple of cases and then try to generalize your result. The idea behind the exponent is that $x^{n+1} = x\cdot x^{n}$ – Alec Dec 12 '13 at 07:17