Induction for f$(n+2)=f(n+1)+6f(n)$ and its property

Question

i'm having real hard time with this:

f:N->N is defined in recursion as following: f(0)=0, f(1)=10, and for ever $n \in N$ $f(n+2)=f(n+1)+6f(n)$.

a) prove by induction (only induction) that $f(n)=2*3^n+(-2)^{n+1}$

b)is f surjective?

what i tried to do:

a)i don't even know how to prove it by induction, so i tried to use common sense. since it's known that $f(0)=0$, $f(1)=10$, then if we input n=0, we get $f(0+2)=f(0+1)+6f(n) -> f(2)=10$. so we'll check for n=1, and get $f(1)=2*3+4=10$ which is valid. now we'll assume that f(n) is true and used it as the basis of induction and try to prove it for the next element, i.e f(n+1): $f(n+1)=2*3^{n+1}+(-2)^{n+2}=2*3^n*3+(-2)*(-2)^{n+1}$, now since we assumed $f(n)=2*3^n+(-2)^{n+1}$ is true, we'll substract $f(n+1)-f(n)$ to get f(1) and we get it's equal to 10. so by using the induction principle we've proven it's true for every $n \in N$

b)after showing f(n) is true, we can use it's properties to assert that for every $y \in Y$ there exists $x \in x$ there's f(x)=y, to claim it's surjective, while considering it's definition, i.e: f:N->N. if we look at f, we see that it is always natural, since $3^n \geq (-2)^{n+1}$, since if $(-2)^{n+1}$ is negative then 3^n will always make it bigger than 0, and if it's positive there would always be a representation of it in N (i don't know how to prove it correctly).

please help me write it correctly. i've written everything i've done and tried to elabroate as much as i can

Answer 1

Use the recurrence to show that as soon as you have two consecutive positive terms the sequence is increasing. Then compute some values and see what happens.

Answer 2

Assume the function expression to be right for $n$ and $n+1$.

$$f(n)=2\cdot3^n+(-2)^{n+1},\\ f(n+1)=2\cdot3^{n+1}+(-2)^{n+2}.$$

Then by the recurrence relation,

$$f(n+2)=f(n+1)+6f(n)=2\cdot3^{n+1}+(-2)^{n+2}+6(2\cdot3^n+(-2)^{n+1})\\ =18\cdot3^n-8\cdot2^n=2\cdot3^{n+2}+(-2)^{n+3}$$ and the function expression is right for $n+2$.

And for the base case,

$$f(2)=2\cdot3^2+(-2)^3=10=f(1)+f(0).$$

---

The function is clearly growing, and there is certainly no $n$ such that

$$f(n)=1.$$

Answer 3

Hints:

• On (a), you have shown the hypothesis formula is true for $n=1$. In this case you need to start by showing it is true for consecutive numbers, so show it is also true for $n=0$ or $n=2$ at the start. Then, assuming it is true for $n=k$ and $n=k+1$, you need to show it is true for $n=k+2$. Combined this provides the proof by induction.

• On (b), the sequence starts $0,10,10,70,130,550,1330,\ldots$. Does this look surjective, i.e. giving every natural number?