Proving this recurrence

Question

Prove that the function $f : \mathbb{N} \to \mathbb{N}$ that satisfies the relation $$f(n + 1) = nf(n) + (n − 1)f(n − 1) +\dots + f(1) + 1,$$ with $f(0) = 1$, it satisfies the relation $f(n + 1) = (n + 1)f(n)$`

In addition, conclude what the function $f$ is.

Can anyone help me solve this recurrence?

Answer 1

Hint. Note that by the given relation, replacing $n+1$ with $n$ , we have $$f(n) = (n-1)f(n-1) + (n − 2)f(n − 2) +\dots + f(1) + 1,$$ Hence $$f(n + 1) = nf(n) + [(n − 1)f(n − 1) +\dots + f(1) + 1]=nf(n) +f(n)=(n+1)f(n).$$ Therefore (for $n\geq 4$), $$f(n)=nf(n-1)=n(n-1)f(n-2)=n(n-1)(n-2)f(n-3).$$ Now are you able to find $f$ such that $f(0)=1$?