Given $T_1 = 0$ and for $i > 1$: $T_i = 1 + \frac{1}{i-1} \sum_{j=1}^{i-1} T_j$ Prove via induction that $T_i = \sum\limits_{j=1}^{i-1} \frac{1}{j}$ 
Given $T_1 = 0$ and for $i \in \mathbb{N}, i > 1$:
\begin{align*}
  T_i &= 1 + \frac{1}{i-1} \sum_{j=1}^{i-1} T_j \\
\end{align*}
Manually computing terms $2,3,4$:
\begin{align*}
  T_2 &= 1 \\
  T_3 &= 1 + \frac{1}{2} \\
  T_4 &= 1 + \frac{1}{3} \left(1 + 1 + \frac{1}{2} \right) = 1 + \frac{1}{2} + \frac{1}{3} \\
\end{align*}
Prove by induction that this is:
\begin{align*}
  T_i &= \sum\limits_{j=1}^{i-1} \frac{1}{j} \\
\end{align*}

The given equation is clearly satisfied for terms $1,2,3,4$. We need to show the inductive step. Assuming it's true for all $j < i$, show that it is also true for $i$.
\begin{align*}
  T_i &= 1 + \frac{1}{i-1} \sum_{j=1}^{i-1} \sum\limits_{k=1}^{j-1} \frac{1}{k} \\
  T_i &= 1 + \frac{1}{i-1} \sum_{j=1}^{i-2} \frac{i-1-j}{j} \\
\end{align*}
 A: $$\begin{align*}
T_{i+1}&=1+\frac1i\sum_{j=1}^iT_j\\
&=1+\frac1i\sum_{j=1}^i\sum_{k=1}^{j-1}\frac1k\\
&=1+\frac1i\sum_{k=1}^{i-1}\sum_{j=k+1}^i\frac1k\\
&=1+\frac1i\sum_{k=1}^{i-1}\frac1k\sum_{j=k+1}^i1\\
&=1+\sum_{k=1}^{i-1}\frac{i-k}{ik}\\
&=1+\sum_{k=1}^{i-1}\left(\frac1k-\frac1i\right)\\
&=1+\sum_{k=1}^{i-1}\frac1k-\frac{i-1}i\\
&=1+\sum_{k=1}^{i-1}\frac1k-1+\frac1i\\
&=\sum_{k=1}^i\frac1k
\end{align*}$$
A: Let's say it is true for $i$, and we want to prove for $i+1$ ($i>1$):
I think you can develop the left hand:
$$T_{i+1} = 1 + \frac{1}{i}\sum_{j=1}^{i}T_j = 1 + \frac{1}{i}\sum_{j=1}^{i-1}T_j + \frac{T_i}{i}$$
$$iT_{i+1} = i + \sum_{j=1}^{i-1}T_j + T_i$$
$$\frac{i}{i-1}T_{i+1} = \frac{1}{i-1} + 1 + \frac{1}{i-1}\sum_{j=1}^{i-1}T_j + \frac{T_i}{i-1}$$
$$\frac{i}{i-1}T_{i+1} = \frac{1}{i-1} + T_i + \frac{T_i}{i-1}$$
$$iT_{i+1} = 1 + (i-1)T_i + T_i$$
$$T_{i+1} = T_i + \frac{1}{i}$$
And that is the right hand:
$$T_{i+1} = \sum_{j=1}^{i}\frac{1}{j} = \sum_{j=1}^{i-1}\frac{1}{j} + \frac{1}{i} = T_i + \frac{1}{i}$$
