Confusion in solving this recursion I am trying to solve the following recursion
$$
\sum _{i=1}^{n-1} -\mu (n-i)+\sum _{i=1}^{n-1} 2 i \mu (n-i)=(n-1)^2 (\mu (n)-1) \tag{1}
$$
By increasing $n$ to $n+1$, we get
$$
\sum _{i=1}^n -\mu (-i+n+1)+\sum _{i=1}^n 2 i \mu (-i+n+1)=n^2 (\mu (n+1)-1) \tag{2}
$$
and then by shifting index, we get
$$
\sum _{i=1}^{n-1} -\mu (n-i)+\sum _{i=1}^{n-1} 2 (i+1) \mu (n-i)+\mu (n)=n^2 (\mu (n+1)-1)\tag{3}
$$
Taking the difference of (1) and (3), we arrive at
$$
-2 \sum _{i=1}^{n-1} \mu (n-i)-\mu (n)=(n-1)^2 (\mu (n)-1)-n^2 (\mu (n+1)-1)\tag{4}
$$
Replace $n$ by $n+1$ and shift index again, we get
$$
(n+1)^2 \mu (n+2)+1= \\2 \sum _{i=1}^{n-1} \mu (n-i)+n^2 \mu (n+1)+2 \mu (n)+\mu (n+1)+2 n+2 \tag{5}
$$
Then taking the difference between (4) and (5), we get
$$
(n+1)^2 \mu (n+2)+(n-2) n \mu (n)=\left(2 n^2+1\right) \mu (n+1)+2 \tag{6}$$
This has a solution
$$
\mu(n)=\frac{2}{3} H_{n-1}:=\frac{2}{3} \sum_{i=1}^{n-1} \frac{1}{i}
$$
What bothers me is that this solution does not fit in the original equation (1)! How is this possible? I don't think I have made a mistake in the computations.
 A: The sums are
$$
\sum _{i=1}^{n-1} -\mu (n-i)+\sum _{i=1}^{n-1} 2 i \mu (n-i)=(n-1)^2 (\mu (n)-1) \tag{1}
$$
Your equation you have arrived
$$
(n+1)^2\mu(n+2)-(2n^2+1)\mu(n+1)+n(n-2)\mu(n)-2=0\tag{eq}
$$
Have indeed general solution
$$
\mu(n)=-1+\frac{2}{3(n-1)}+\frac{2}{3}H_{n-2}+C_1+C_{2}\left(-\frac{1}{2}\psi^{(1)}(n-2)+\frac{\pi^2}{12}+\frac{-12+43n-46n^2+20n^3-3n^4}{4(2-3n+n^2)^2}\right)\tag{sol}
$$
as long as $n\geq 3$. That is because for $n=1,2$ the solution has singularities at $n=1$ and $n=2$ ($n=2$ is also a curious point since $H_n=\sum_{1\leq n\leq n}k^{-1}$ and by convection we use $H_0=0$). It is like beeing solving a two order differential equation with no initial conditions. The solution it can be far away from what you might expecting. The Mathematica do its best. Its gives you $-1+\frac{2}{3(n-1)}+\frac{2}{3}H_{n-2}+C_1$ and not $C_1+\frac{2}{3}H_{n-1}$, to tell you that $n=1$ and $n=2$ are pathological cases. Hence for $n\geq 3$ the solution goes well. But for $n=1,2$ you have to define or give more input. The values at $n=1$ and $n=2$ are usefull for your computation of the sums you have. By demanding your sums to be in accordance to each other you can define
$$
\mu(n)=\left\{\begin{array}{cc}
c_1\textrm{ , for } n=1\\
c_2\textrm{ , for }n=2\\
2/3H_{n-1}-1\textrm{ , for }n\geq 3
\end{array}\right\}\tag 2
$$
where $H_0=0$. Setting these into (eq) and (1), you take a solution: $c_1=-5/4$, $c_2=-1/4$.
A: If you look at the derivation from (1) to (6) carefully, you would see that the argument can only go one direction. Any solution of (1) must satisfy (6), but not the other way around.
