Prove that $R(n) =\frac{2}{n}\sum_{k=0}^{n-1} (R(k))+c$ is $R(n) = n*c$

Question

I have to transform this recursive function $$R(n) =\frac{2}{n}\sum_{k=0}^{n-1} (R(k))+c$$ into a closed formula

I found $R(n) = n*c$ that looks like it fits, but I don't know how to prove it.

I have tried induction but failed when i was at

$$R(n+1)=\frac{2}{n+1}R(n)+\frac{2}{n+1}\sum_{k=0}^{n-1}(R(k))+c$$

i have a problem to finish. Do you have a tip for me?

(May $\sum_{i=1}^{n} \frac{1}{i(i+1)}=\frac{n}{n+1}$ help me?)

Answer 1

Write the recurrence as:

$$n \, R_n = 2\,\sum_{k=0}^{n-1} R_k+ n\,c$$

Subtracting the relations for $n$ and $n-1$:

$$ \begin{align} & n \, R_n - (n-1)\,R_{n-1} = 2\,R_{n-1}+ c \\[3px] \iff\;\; & n\,R_n = (n+1)\,R_{n-1} + c \\[3px] \iff\;\; & \frac{R_n}{n+1} = \frac{R_{n-1}}{n} + \frac{c}{n(n+1)} \end{align} $$

Adding up the latter from $1$ to $n$ and telescoping:

$$ \frac{R_n}{n+1} = \frac{c}{n(n+1)} + \frac{c}{(n-1)n}+ \cdots + \frac{c}{1 \cdot 2} + R_0 = c \cdot \frac{n}{n+1} + R_0 $$

May $\sum_{i=1}^{n} \frac{1}{i(i+1)}=\frac{n}{n+1}$ help me?

Indeed, that was used in the very last step.