Prove a recursively defined function property by induction Let $f(n + 1) = f(n) + nf(n -1)$ for $n \geq 2$ where $f(1) = 1$, $f(2) = 2$. 
Prove that $f(n) \leq n!$. I'm struggling to understand the reasoning behind the algorithm.
Professor says:
(0) Show that the formula works for the initial conditions:
For $f(1):$
$$(1+1)! \leq 1! + 1 \cdot (1 - 1)!$$
$$2 \leq 2.$$
For $f(2):$
$$(2 + 1)! \leq 2! + 2 \cdot (2 - 1)!$$
$$6 \leq 4.$$
And this already fails for some reason. Nevermind. Let's get to the second step.
(1) Let $n \geq 2$. Suppose that $V(k): f(k) \leq k!$ where $k = n - 1$.
Then he does something. I tried to recreate it:
$$f(n + 1) \leq n! + n \cdot (n - 1)!$$
$$f(n + 1) \leq n! + n!$$
$$f(n + 1) \leq 2n!.$$
I know that I should somehow get to $f(n + 1) \leq (n + 1)!$ but I just don't understand how and why. There is no way I'm getting from $2n!$ to $(n + 1)!$. Any hints?
 A: $$f(1)=1\ge1!$$
$$f(2)=2\ge2!$$
$$f(3)=f(2)+2f(1)=4\not\ge3!$$
$$f(4)=f(3)+3f(2)=10\not\ge4!$$
The claim seems false for all following integers.

The modified claim is true, $2n!\le(n+1)!$ for $n\ge2$.
A: Let the proposition be true for $k$ such that :
$$f(k) \le k! \tag 1$$
Adding $k f(k-1)$ on both the sides :
$$f(k+1) \le k! + kf(k-1)$$
Now we have to show that  $$(k+1)!\ge k! + kf(k-1)$$
Which follows from the fact that $$k\cdot k! \ge k f(k-1)$$
Note that the last inequality is true because of $(1)$ as $f(n)$ is a strictly increasing function.
A: 
There is no way I'm getting from 2n! to (n+1)!

$2(n!) \le (n+1)!$.
So $f(n+1) \le n! + n! =2(n!) \le (n+1)*n! = (n+1)!$.
....
As for $n =1$ and $f(1) = 1 =1!$ and 
And $n =2$ and $f(2) = 2 = 2!$.
And that is ALL.
Why is the professor doing that crap about trying to prove the wrong result that $(n+1)! \le n! + n(n-1)!$.  1) That's not relevant and $f(n)$ doesn't equal $n!$ so why would we care and 2)  It's obviously not true:  $n! + n(n-1)! = n! + n! = (n!)*2 < n!(n+1) = (n+1)!$ whenever $n > 1$.
A: This is a proof by induction with two base cases.  $f(1)$ and $f(2)$ true by definition.  All that is left to prove is that if $$f(k) \le k!$$ for any fixed integer $k > 2$, then $$f(k + 1) \le (k + 1)!.$$  The last line of the proof is $f(k+1) \le 2 k!$.  If $k > 2$ then $$2 \cdot k! < k \cdot k! < (k + 1)!.$$
A: Just plug in the function for $f(k) = k!$ and form a chain of true expressions leading to $(k + 1)!$:
$$f(n + 1) = n! + n \cdot (n - 1)! = n! + n! \leq n \cdot n! + n! = n! \cdot (n + 1) = (n + 1)!. $$
