How can I use induction to prove that this recursive definition is correct?

Question

How can I use induction to prove that this recursive definition is correct?

$f(n)=4n-2$ for $n≥1$

Recursive definition:

1) $f(1)=2$

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

Now I have to use induction to prove that the recursive definition is correct but I don't know how to do it since $f(n)$ is not equal to anything.

Answer 1

Let $f$ be defined as in your question and let $g$ be defined recursively by $g(1)=2$ and $g(n)=g(n-1)+4$.

Then it is enough to prove by induction that $g(n)=f(n)$ for positive integers.

The base case is just the observation that $g(1)=2=f(1)$.

Now the induction step:

If $g(n)=f(n)=4n-2$ then $g(n+1)=g(n)+4=4n-2+4=4n+2=f(n+1)$.

Answer 2

HINT

We have that for the base case

• $f(1)=2$ by recursive relation

• $f(1)=4-2=2$ by formula

for induction step we assume true

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

and we need to prove that

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