# Induction Proof with Indices | Principles of Mathematical Induction

Prove $1 \times 2 + 2 \times 2^2 + 3 \times 2^3 + \cdots + n \times 2^n = (n-1) \times 2^{n+1} + 2$.

## Step 1

Show it is true for $n=1$.

\begin{align} &\text{LHS} = 1 \times 2 = 2 \\ &\text{RHS} = (1-1) \times 2^{1+1} +2 = 2 \\ &\text{LHS} = \text{RHS} \\ &\text{Therefore it is true for } n=1 \end{align}

## Step 2

Assume that it is true for $n=k$.

$\text{That is, } 1 \times 2 + 2 \times 2^2 + 3 \times 2^3 + \cdots + k \times 2^k = (k-1) \times 2^{k+1} + 2$

## Step 3

Show it is true for $n=k+1$.

$\text{That is, } 1 \times 2 + 2 \times 2^2 + 3 \times 2^3 + \cdots + k \times 2^k + (k+1) \times 2^{k+1}= k \times 2^{k+2} + 2$

\begin{align} \text{LHS} &= 1 \times 2 + 2 \times 2^2 + 3 \times 2^3 + \cdots + k \times 2^k + (k+1) \times 2^{k+1} \\ &= (k-1) \times 2^{k+1} + 2 + (k+1) \times 2^{k+1} \\ &= \left[ (k-1)+(k+1) \right] \times 2^{k+1} + 2 \\ &= 2k \times 2^{k+1} +2 \\ &= k \times 2^{k+2} + 2 \\ &= \text{RHS} \\ &\text{Therefore it is true for } n = k+1 \\ &\text{Therefore formula is true for all integers } n \ge 1. \end{align}