Find a formula for $f(n)$ and prove it by induction

Question

The following Problem:

«Find a formula for $f(n)$ and prove it by induction»

1. $f(0) = 0$ and $f(n) = f(n-1) -1$
2. $f(0) = 0$ and $f(1) = 1$ and $f(n) = 2*f(n-2)$

For the first one I thought of $f(n) = -n$

The induction basis holds: $f(0) = -(0) = 0$.

For the step I get: $f(n) = -n$

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

so I get $-2n-1 = f(n+1)$ instead of $-n-1$

Where is my fault in the induction?

For the Problem 2 I'm asking for some hints! For every odd number the function is $0$, so I thought of something $((-1)^{n+1}+1)$ times something.

Thanks a lot Community!

Answer 1

As for problem 2:

By hand, you can check that the first terms of the sequence is going to look like:

$$0,1,0,2,0,4,0,8,0,16,\ldots$$

Killing the first and every other term with a factor of $(-1)^{n+1}+1$ works fine (but be aware that this factor becomes $2$ for odd $n$).

You need an expression which goes through the different powers of $2$, but only for odd $n$'s, so $2^n$ won't work. Can you see what will work?

Answer 2

Thanks a lot for the hint. I got the following idea:

$((-1)^{n+1}+1)2^{((n+1)/2)-2}$

I think this guy works out just fine!