Aligning stackrel signs beneath each other using split

You can use \mathmakebox or \mathclap (thanks to Andrew) from mathtools

\documentclass{article}
\usepackage{mathtools}

\begin{document}
\begin{equation*}
\begin{split}
S_n &=                 2^iS_{n-i}+2^i-1\\
    &\stackrel{\mathmakebox[\widthof{=}]{\mathrm{IH}}}{=}  2^i(2^1S_{n-i-1}+2^1-1)+2^i-1\\
    &=                 2^{i+1}S_{n-i-1}+2^{i+1}-1
\end{split}
\end{equation*}
\end{document}

You can use align* also instead of equation* and split

\documentclass{article}
\usepackage{mathtools}

\begin{document}
\begin{align*}
S_n &=                 2^iS_{n-i}+2^i-1\\
    &\stackrel{\mathclap{\mathrm{IH}}}{=}  2^i(2^1S_{n-i-1}+2^1-1)+2^i-1\\
    &=                 2^{i+1}S_{n-i-1}+2^{i+1}-1
\end{align*}
\end{document}

Please note that I have changed IH to \mathrm{IH}. (Thanks to egreg).

In fact, the solutions above are not optimal because the example given is a very special case: IH has almost the same width as =, so there is no problem on the right side. But consider what happens when we need something significantly larger than IH, like in

\begin{align*}
S_n &= 2^iS_{n-1}+2^i-1\\
&\stackrel{\mathrm{IH,IG,IK,IL}}{=}2^i(2^1S_{n-i-1}+2^1-1)+2^i-1\\
&= 2^{i+1}S_{n-i-1}+2^{i+1}-1
\end{align*}

Then the right part of IH,IG,IK,IL will overlap on the formula!

My solution is to define \leftstackrel, which aligns perfectly on the left but adds the necessary white space on the right so that there is no overlap. Here is the code:

\newlength{\leftstackrelawd}
\newlength{\leftstackrelbwd}
\def\leftstackrel#1#2{\settowidth{\leftstackrelawd}%
{${{}^{#1}}$}\settowidth{\leftstackrelbwd}{$#2$}%
\addtolength{\leftstackrelawd}{-\leftstackrelbwd}%
\leavevmode\ifthenelse{\lengthtest{\leftstackrelawd>0pt}}%
{\kern-.5\leftstackrelawd}{}\mathrel{\mathop{#2}\limits^{#1}}}

and it can be used simply as:

\begin{align*}
S_n &= 2^iS_{n-1}+2^i-1\\
&\leftstackrel{\mathrm{IH,IG,IK,IL}}{=}2^i(2^1S_{n-i-1}+2^1-1)+2^i-1\\
&= 2^{i+1}S_{n-i-1}+2^{i+1}-1
\end{align*}

Compare (1.1) (legacy \stackrel), (1.2) (\stackrel proposed above) and (1.3) (\leftstackrel) in the figure below

_{(source: fluxus-virus.com)}

I suggest three strategies. The first one is to define a command \iheq that prints an equals sign with some padding to become the same width as \overset{\mathrm{IH}}{=}, which can be simply obtained with \iheq*.

The second strategy is adding “(IH)” to the side.

\documentclass{article}
\usepackage{amsmath}
\usepackage{xparse}

\NewDocumentCommand{\iheq}{s}{%
  \overset{\IfBooleanTF{#1}{\mathrm{IH}}{\hphantom{\mathrm{IH}}}}{=}%
}

\begin{document}

\begin{equation*}
\begin{split}
S_n &\iheq  2^iS_{n-i}+2^i-1\\
    &\iheq* 2^i(2^1S_{n-i-1}+2^1-1)+2^i-1\\
    &\iheq  2^{i+1}S_{n-i-1}+2^{i+1}-1
\end{split}
\end{equation*}

\begin{equation*}
\begin{aligned}
S_n &= 2^iS_{n-i}+2^i-1\\
    &= 2^i(2^1S_{n-i-1}+2^1-1)+2^i-1 && \makebox[0pt][l]{(IH)}\\
    &= 2^{i+1}S_{n-i-1}+2^{i+1}-1
\end{aligned}
\end{equation*}

\end{document}

Third strategy: make IH smaller and ensure it's zero width.

\documentclass{article}
\usepackage{amsmath}
\usepackage{xparse}

\NewDocumentCommand{\iheq}{s}{%
  \IfBooleanTF{#1}{\overset{\IH}{=}}{=}%
}
\NewDocumentCommand{\IH}{}{%
  \hidewidth\scriptscriptstyle\mathrm{IH}\hidewidth
}

\begin{document}

\begin{equation*}
\begin{split}
S_n &\iheq  2^iS_{n-i}+2^i-1\\
    &\iheq* 2^i(2^1S_{n-i-1}+2^1-1)+2^i-1\\
    &\iheq  2^{i+1}S_{n-i-1}+2^{i+1}-1
\end{split}
\end{equation*}

\end{document}