I have an assignment where I need to bring the following recursive equation in a closed form:
$$R(n) = \dfrac{2}{n} \cdot (R(0) +R(1) +. . .+R(n−1)) + c$$
I can use
$$\sum_{i=1}^{n} \dfrac{1}{i(i+1)} = \dfrac{n}{n+1}$$
from a previous assignment.
So far I came to $nR(n)=2(R(0) +R(1) + \cdots +R(n−1)) + cn$
and then to
$(n-1)R(n-2)=2(R(0) +R(1) + \cdots +R(n−1)) + c(n-1)$
But I have no idea how to continue and how to use the other equation.
Any help is appreciated.
Sometimes it helps to just plot a few values:
$R(0) = 0$
$R(1) = \frac{2}{1} \cdot 0 + c = c$
$R(2) = \frac{2}{2} \cdot (0 + c) + c= 2c$
$R(3) = \frac{2}{3} \cdot (0 + c + 2c) + c = 3c$
$R(4) = \frac{2}{4} \cdot (0 + c + 2c + 3c) + c= 4c$
$R(5) = \frac{2}{5} \cdot (0 + c + 2c + 3c + 4c) + c= 5c$
Which strongly suggests that $R(n) = nc$. Let's prove it by induction:
Base case: $R(0) = 0 \cdot c = 0$, which is true. And likewise $R(1) = 1 \cdot c = c$, which is true.
Inductive step: For all $0<n$ up to this point, suppose $R(n) = c + \frac{2}{n} \cdot \sum_{i=0}^{n-1}R(i) = nc$. Let's show that $R(n+1) = (n+1) \cdot c$
Then we have:
$$R(n+1) = c + \frac{2}{n+1} \cdot \sum_{i=0}^{n} R(i) = c + \frac{2}{n+1} \sum_{i=0}^{n}ic \\= c + \frac{2}{n+1} \cdot \frac{1}{2}cn(n + 1) = (n+1) \cdot c$$
Which proves the result.