Question about recursive algorithm

Question

I have following problem:

$$f(n)=\frac{1}{1^2+1}+\frac{2}{2^2+1}+\frac{3}{3^2+1}+\cdots+\frac{n}{n^2+1}$$

• Write recursive algorithm for $f(n)$
• Prove that recursive algorithm is correct
• Count steps

I don't know where to start, any hints about how to approach this problem would be greatly appreciated. I need most help on first and third question, It probably will be easy to prove the equation by induction as the second question asks. Thanks in advance

Answer 1

Do you mean writing an algorithm that calculates $ f(n) $?

float sum(n) {
if (n==0) return 0
else return sum(n-1) + n/(n*n + 1)
}