Solve the recurrence relation : $f(n) = 1 + \frac{f(n) + f(n-1) + \cdots + f(1)}{n+1}$

Question

For naturals $n$, $f(n) = 1 + \dfrac{f(n) + f(n-1) + \cdots + f(1)}{n+1}$. What is $f(n)$? This is not a homework problem. Is there a general method to solve these recurrence relations? I will appreciate if someone directs me to a short tutorial/book to learn about solving recurrence relations.

Answer 1

Not an answer...

Let $f_n = f(n)$. Then $$ f(n) = 1 + \dfrac{f(n) + f(n-1) + \cdots + f(1)}{n+1} \\ f_n = n+1+ \frac{f_n + \sum_{i=1}^{n-1} f_i}{n+1} \\ n f_n + f_n = n+1 + f_n + \sum_{i=1}^{n-1} f_i \\ nf_n = \sum_{i=1}^{n-1} f_i + n +1 \\ f_n = \frac{\sum_{i=1}^{n-1} f_i + n +1}{n}\\ f_n = \frac{\sum_{i=1}^{n-1} f_i +1}{n} + 1. $$

That might be more useful for some approaches.

Answer 2

In a matrix-scheme the given equality looks like $$ \small \begin{array}{} \; & &\begin{array} {|r|} 1\\f(1)\\f(2)\\f(3)\\ \vdots \end{array} \\ & * & \\ \begin{array} {r|rrrrr|} & 1 \\ \phantom{f(1)} & 1 & 1/2 \\ \phantom{f(1)} & 1 & 1/3 & 1/3\\ \phantom{f(1)} & 1 & 1/4 & 1/4 & 1/4\\ & \vdots & \vdots & \vdots & \vdots & \ddots\\ \end{array} & = & \begin{array} {|r|} 1\\f(1)\\f(2)\\f(3)\\ \vdots \end{array} \\ \end{array}$$ The sequence is obviously the normed eigenvector with the eigenvalue 1 of the bottom-left matrix.

The eigenvector (thus the solution for your function at positive integers) begins then with $[1,2,5/2!,17/3!,74/4!,...]$ which means $f(1)=2$, $f(2)=2.5$ etc.

I just found a good explanation for the general term, I've got with the (unsigned) Stirlingnumbers first kind as sequence $s_{1:r,2}=\{0,1,3,11,50,274,...\}_{r \ge 0}$ $$f(k) =_{k \ge 0} 1+ s_{1:k,2}/k! \qquad \qquad f(0)=1$$

Looking at this in terms of generating-functions we find that $$ g(x) = \sum_{k=0}^\infty f(k) x^k \qquad \underset {|x| \lt 1}{=} \qquad {1\over1-x} + {-\log(1-x) \over 1-x} $$

---

Remark: the matrix-ansatz proved useful for me in many instances, so I think it's often useful to approach similar problems with this method (of course only when a simpler one runs into the void...). A very well known example where a recursion is handled (and indepth studied) by the matrix-method is the Fibonacci-sequence, and that matrix-solution leads then also very naturally to a Binet-type formula. If you are interested in more examples you can find some other answers of mine here in MSE. For the matrix-method with the Fibonacci sequence there is very nice and exhaustive material at Rob Johnsons's website.