Induction and Recursion: $f(1)=2$ and $f(n)=f(n-1)+2n$ for $n>1$

Question

I have bad time with induction and recursion and I have an exam soon.

We have this: $$f(1)=2$$ $$∀n>1:f(n)=f(n-1)+2n$$

We need to proof that is the solution of f(n)=f(n-1)+2n,f(1)=2 is:

(the solution need be prooven with induction)

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

solution:

Base case:

n=1:

$$f(1)=2$$ $$f(1)=1(2)$$

We can assume that:

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

Inductive Step:

I don't know what to do next??

Any help will be appreciated!

Answer 1

We have: $$f(n)=f(n-1)+2n$$ And we need to prove: $$f(n)=n(n+1)$$ Now let's check for $n=1$: $$f(1)=1(1+1)=2$$ Now let's assume it's correct for n, i.e. that $f(n)=n(n+1)$, so we can use it. $$f(n-1)+2n=n(n+1)$$ Now let's prove for $n+1$: $$f(n+1-1)+2(n+1)=(n+1)(n+2)$$ $$f(n)+2n+2=(n+1)(n+2)$$ Now we can use the assumption, and substitute $f(n)$ with it's assumed value $n(n+1)$: $$n(n+1)+2n+2=(n+1)(n+2)$$ $$n^2+n+2n+2=n^2+3n+2$$ $$n^2+3n+2=n^2+3n+2$$ And that's correct.

Now by the Induction Axiom, we proved the theorem.

Answer 2

In order to prove $$f(n)=n(n+1)$$ for all $n \geq 1$ by induction:

• Base case: Show that $f(1)=1 \times (1+1)$.

• Inductive step: We assume the inductive hypothesis that $f(k)=k(k+1)$ and use this to show $f(k+1)=(k+1)(k+2)$ using the identity $f(k+1)=f(k)+2(k+1)$.

Then we conclude, by induction, that $f(n)=n(n+1)$ holds for all $n \geq 1$.