Prove a recursively defined function property by induction

Question

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?

Answer 1

$$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$.

Answer 2

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$.

Answer 3

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.

Answer 4

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)!.$$

Answer 5

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)!. $$