Given a function $f(i)$ defined as $\sum_{r=0}^i P(i, r)$ where $P(i, r)$ is the number of permutation from $i$ items choose $r$, the following recurrence seems to hold: $$f(n) = nf(n-1) + 1$$ A few first values:
\begin{align}
f(0) = &\; P(0, 0) = 1\\
f(1) = &\; P(1, 0) + P(1, 1) = f(0)+1 = 2\\
f(2) = &\; P(2,0) + P(2,1) + P(2,2)= 2f(1)+1 = 5\\
f(3) = &\; P(3,0)+ \dots +P(3,3) = 3f(2)+1 = 16
\end{align}
I got this recurrence by writing a program and trying to see the pattern, and it seems to be correct. But how to derive it algebraically? Also, is there a nice combinatorial argument for this? Like maybe the equation describes "how to choose $i$ people from a pool of $n$ people while designating a leader" or something.
Thanks in advance!
First notice that $$P(n,r) = \frac{n!}{(n−r)!},$$ so that $$f(n)=\sum_{r=0}^n P ( n , r )=\sum_{r=0}^n \frac{n !}{ ( n − r ) !},$$ and $$f(n-1)=\sum_{r=0}^{n-1} P ( n-1 , r )=\sum_{r=0}^{n-1} \frac{(n-1) !}{ ( n-1 − r ) !}.$$ It follows that \begin{align} nf(n-1)+1 =&\;n\sum_{r=0}^{n-1} \frac{(n-1) !}{ ( n-1 − r ) !}+1\\ =&\;\sum_{r=0}^{n-1} \frac{n !}{ ( n − (1+r) ) !} +1\\ =&\;\sum_{r=1}^{n} \frac{n !}{ ( n − r ) !} +1\\ =&\;\sum_{r=0}^{n} \frac{n !}{ ( n − r ) !} \\ =&\;f(n).\\ \end{align}