 Solution

Use rightmost-first composition of permutations, and letFor $n\ge 2$, direct evaluation gives $ab=(1n)$. Conjugating this transposition by powers of $a$ yields the transpositions between consecutive letters around the cycle, including $(12),(23),\dots ,(n-1n)$.

Put $s_i=(ii+1)$. For $i<j$,Thus the adjacent transpositions generate every transposition, and permutation cycle decomposition shows that transpositions generate the symmetric group. Therefore $⟨a,b⟩=S_n$.

For the final lower bound, associate a graph to a family of transpositions: its vertices are the letters and its edges are the swapped pairs. Every generator preserves every connected component, so generation of $S_n$ requires that graph to be connected. A connected graph on $n$ vertices needs at least $n-1$ edges: adding an edge can reduce the number of components by at most one, starting from $n$ isolated vertices. The adjacent transpositions supply exactly $n-1$ edges. Equivalently, transpositions on a connected graph generate the symmetric group. Hence