$A_N = 1 + \frac{2}{N} \sum_{1 \leq j \leq N} A_{j-1}$ for $N>0$
I have tried only one step which is multiply the equation by $N$,
i.e. $NA_N = N + 2 \sum_{1 \leq j \leq N} A_{j-1}$,
then I'm lost.
Would anyone like to continue solving please? I'm really confused about quicksort and recurrence relation.
The standard trick to deal with recurrences that have a sum involving the previous term is to subtract two instances of the recurrence. Here, we have:
\begin{align} NA_N &= N + 2 \sum_{j=1}^N A_{j-1} \\ (N-1)A_{N-1} &= N-1 + 2 \sum_{j=1}^{N-1} A_{j-1} \\ NA_N - (N-1)A_{N-1} &= 1 + 2\left(\sum_{j=1}^N A_{j-1} - \sum_{j=1}^{N-1} A_{j-1}\right) \\ &= 1 + 2 A_{N-1}. \end{align} This gives us the recurrence $NA_N - (N-1) A_{N-1} = 1 + 2 A_{N-1}$, which we can simplify to $NA_N = 1 + (N+1)A_{N-1}$ or (slight hint) $\frac{A_N}{N+1} = \frac{A_{N-1}}{N} + \frac1{N(N+1)}$.
See if you can take it from here.