Проверим базу индукции:
Положим, $%n = 1$%, тогда $%{2^0} = {2^1} - 1 \Leftrightarrow 1 = 1$% верно!
Возьмем такое целое число $%k > 1$% и предположим, что утверждение верно для $%n = k$%. Тогда по нашему предположению верно должно быть и утверждение: $%1 + 2 + {2^2} + \cdots + {2^{k - 1}} = {2^k} - 1$%. Сделаем индукционный шаг $%k = k + 1$% и докажем, что выражение $%1 + 2 + {2^2} + \cdots + {2^k} = {2^{k + 1}} - 1 = 2 \cdot {2^k} - 1$% верно. Прибавим к обеим частям индукционного предположения число $%{2^k}$%, тогда получим:
$%1 + 2 + {2^2} + \cdots + {2^{k - 1}} + {2^k} = {2^k} - 1 + {2^k} = 2 \cdot {2^k} - 1 = {2^{k + 1}} - 1$%. Тем самым мы доказали, что из $%k \to k + 1$%, следовательно на основе доказанного индукционного шага мы вправе заявить, что $%1 + 2 + {2^2} + \cdots + {2^{n - 1}} = {2^n} - 1$% справедливо при любых натуральных числах $%n \in N$%.
Это один из самых простых примеров такого сорта. Прибавьте к обеим частям $%2^n$% и упростите правую часть (это основной шаг).