Prove that on average, n-permutations have $H_n$ cycles, where $H_n=1+1/2+1/3+...+1/n$ without mathematical induction.
I think that on average, the number of cycles of length i (1≤i≤n) should be 1/i to prove but, I don't know how to show this. Some books proved this using an indicator function. Do I have to use that?
On
The first step is to show that the distribution of the length of the cycle containing $1$ is uniform. Indeed, the number of permutations in which $1$ is in a cycle of length $t$ is $$ (n-1)(n-2)\cdots(n-t+1)\cdot(n-t)! = (n-1)!. $$ Here $(n-1)(n-2)\cdots(n-t+1)$ counts the number of possible cycles containing $1$ of length $t$, and $(n-t)!$ counts the number of permutations on the remaining elements.
For a fixed permutation $\pi$, define $X_i$ (for $i \in \{1,\ldots,n\}$) to be the reciprocal of the length of the cycle containing $i$. It is not too hard to see that $\sum_{i=1}^n X_i$ is the number of cycles in $\pi$ (exercise). If $\pi$ is chosen randomly, the calculation above shows that $$ \mathbb{E}[X_i] = \sum_{t=1}^n \frac{1}{n} \cdot \frac{1}{t} = \frac{1}{n} H_n. $$ By linearity of expectation, we deduce that $$ \mathbb{E}\left[\sum_{i=1}^n X_i\right] = H_n. $$
On
No, you don't "HAVE" to use indicators, you GET to use indicators. It's a wonderfully nice and easy method and you should be glad whenever you can use it. And it works like a charm on this problem.
The expected number of cycles of length $i$ is equal to the number of sets of size $i$, which is $\binom ni,$ times the probability that a given set of size $i$ is permuted cyclically by a random permutation of $\{1.2,\dots,n\},$ which is $(i-1)!(n-i)!/n!.$ That is, the expected number of cycles of length $i$ is $$\binom ni\frac{(i-1)!(n-i)!}{n!}=\frac1i$$ and so the expected number of cycles of all lengths is $$\sum_{i=1}^n\frac1i=H_n.$$
On
By way of promoting symbolic combinatorics here is the species of permutations with all cycles marked: $$\mathfrak{P}(\mathcal{U}\mathfrak{C}(\mathcal{Z})).$$ This translates to the bivariate generating function $$G(z, u) = \exp\left(u\log\frac{1}{1-z}\right).$$ We require $$n! [z^n] \left.\frac{\partial}{\partial u} G(z,u)\right|_{u=1}.$$ This is $$n! [z^n] \left.\exp\left(u\log\frac{1}{1-z}\right)\log\frac{1}{1-z}\right|_{u=1}$$ or $$n! [z^n] \frac{1}{1-z} \log\frac{1}{1-z} = n! \times H_n.$$ It follows that the desired average is $$H_n.$$
Remark. It is generally known that the exponential generating function produces the average on differentiation and substitution (EGF turns into OGF). I included it nonetheless to aid the reader.
One can write down the disjoint cycle representation of every permutation in $S_n$ and then tally the total number of $k$-cycles seen. For every possible $k$-cycle $\sigma$ we can count the number $N(\sigma)$ of permutations which contain $\sigma$ in its cycle representation, and then sum over all such $\sigma$. The permutations of the set $\{1,\cdots,n\}$ with $\sigma$ in its cycle representation are in bijection with the permutations of $\sigma$'s fixed points, of which there are $(n-k)!$, and so $N(\sigma)$ doesn't actually depend on $\sigma$! So, compute the number of $k$-cycles $\sigma$ in $S_n$, multiply this by $(n-k)!$ and divide by $n!$ to get the average number of $k$-cycles.