Given the function $f (n) = 1 + (-1)^n$ for $n ≥ 1$

Question

Given the function $f (n) = 1 + (-1)^n$ for $n ≥ 1$.

a) Define recursively the function $f (n)$.

b) Use induction to prove that the given definition is correct. Say what kind of induction has been used.

My attempt:

a) For $f(1)=1+(-1)^1=1-1=0$. For $f(n-1)=1+(-1)^{n-1}=1+\frac{(-1)^n}{-1}=1-(-1)^n$. So I think $1-(-1)^n$ is the recursive definition.

b) I don't know what to do. The induction is the same method as the above, it's just $n+1$ so I don't know what the exercise expects me to do.

Answer 1

You need to find a relation between $f(n)=1+(-1)^n$ and $f(n+1)=1+(-1)^{n+1}$, i.e. some function $g$ such that $f(n+1)=g(f(n))$.

Notice that $(-1)^{n+1}=-(-1)^n$, so that

$$f(n+1)-1=-(f(n)-1)$$

and

$$f(n+1)=2-f(n).$$

Answer 2

$$f(n+1)-1 = (-1)^{n+1} = (-1)(-1)^n = -(f(n)-1)$$

so

$$f(n+1) = -f(n)+2$$

and $f(1)= 0$

Answer 3

The goal of recursion is to find a relationship between $f(n)$ and $f(n-1)$. So you have

\begin{align} f(n) &= 1 + (-1)^n \\ f(n-1) &= 1 + (-1)^{n-1} = 1 - (-1)^n \end{align}

There are two ways you can go. Subtracting the 2 equations yields $$ f(n) - f(n-1) = 2(-1)^n $$

Therefore $$ f(n) = f(n-1) + 2(-1)^n $$

The second way is to add them instead, which gives $$ f(n) + f(n-1) = 2 $$

Then $$ f(n) = 2 - f(n-1) $$

Both of these are correct, since the sequence goes $0,2,0,2,0,2\dots$

---

For the induction, the basic process goes like this

• Prove the formula holds for $n=1$

• Suppose the formula holds for some integer $n=k$, then prove it must also hold for $n=k+1$

I'll leave this part to you.