# Mathematical Induction

The simple case of 'weak' induction.

1. Prove the Base Case k=b
2. Prove that, assuming it holds for some case $k$, it also holds for $k+1$



- It holds for $k=b$. (step 1)
- If it holds for $k=b$ then it should hold for $k=b+1$. (step 2)

- Therefore, it holds for $k=b+1$. (step 1 + step 2)

- If it holds for $b+1$ then it holds for $b+2$. (step 2)

- If it holds for $b+2$ then it holds for $b+3$. (step 2)
.
.
.

And so on.


### Example:

The proposition is that:

\begin{equation}
P(n) = \sum_{i=0}^{n-1} b^i = \frac{1-b^n}{1-b}
\end{equation}

#### Base Case: Prove that it Holds for n = 1

\begin{equation}
P(1) = \sum_{i=0}^{1-1} b^i = b^0 = \frac{1-b^1}{1-b} = 1
\end{equation}

This proves the base case.

#### Step Case: Prove that if it holds for n=k then it also holds for n=k+1

Assume the following to be true:
\begin{equation}
P(n) = \frac{1-b^n}{1-b}
\end{equation}

\begin{equation}
P(k+1) = P(k) + b^{k} =  \frac{1-b^k}{1-b} + \frac{(1-b)b^{k}}{1-b} = \frac{1-b^k+b^k+b^{k+1}}{1-b} = \frac{1-b^{k+1}}{1-b}
\end{equation}

This proves the step case.




e0a591fc0067b51473f5b570f238e742c45d8164
ipynb
Jupyter Notebook
Math - Mathematical Induction.ipynb
jpbm/probabilism
a2f5c1595aed616236b2b889195604f365175899
MIT
Math - Mathematical Induction.ipynb
jpbm/probabilism
a2f5c1595aed616236b2b889195604f365175899
MIT
Math - Mathematical Induction.ipynb
jpbm/probabilism
a2f5c1595aed616236b2b889195604f365175899
MIT
Qwen/Qwen-72B
1. YES
2. YES