\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}

\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{axiom}{Axiom}

\title{Examples for Proof Techniques II}
\author{Gabi Röger}
\date{}

\begin{document}
\maketitle

\section{Proof by Induction}

We will consider two ways of proving the following theorem by induction:

\begin{theorem}
For every $n\in\mathbb N_0$ it holds that if $n$ is odd then $7^n + 3^n$ is divisible by $10$.
\end{theorem}

\begin{proof}
We show this by induction.

We use proposition $P(n)$: ``if $n$ is odd then $7^n + 3^n$ is divisible by $10$''.
\medskip

\noindent\emph{Base case $n=0$:} $P(0)$ is trivially true because $0$ is not odd.

\noindent\emph{Base case $n=1$:} $P(1)$ is true because $7^1 + 3^1 = 10$ is divisible by $10$.
\medskip

\noindent\emph{Induction hypothesis:} Suppose $P(k)$ is true for all $0\leq k \leq n$.
\medskip

\noindent\emph{Inductive step: $n \rightarrow n + 1$}:
\smallskip

If $n+1$ is even, $P(n+1)$ is trivially true.
\smallskip

If $n+1$ is odd, we need to show that $7^{n+1} + 3^{n+1}$ is divisible by $10$.

\begin{align*}
    7^{n+1} + 3^{n+1} &= 7^2\cdot 7^{n-1} + 3^2\cdot 3^{n-1}\\
        &= 49\cdot 7^{n-1} + 9\cdot 3^{n-1}\\
        &= 40\cdot 7^{n-1} + 9\cdot 7^{n-1} + 9\cdot 3^{n-1}\\
        &= 40\cdot 7^{n-1} + 9(7^{n-1} + 3^{n-1}) =: (*)
\end{align*}

Since $n+1$ is odd, also $n-1$ must be odd, so by the induction hypothesis we know that there is an integer $k$ such that $10k = 7^{n-1} +  3^{n-1}$.
With this $k$, it holds that
\begin{align*}
 (*) = 40\cdot 7^{n-1} + 9(7^{n-1} + 3^{n-1}) &= 40\cdot 7^{n-1} + 9\cdot 10k \\
 &= 10\cdot 4\cdot 7^{n-1} + 10\cdot 9k\\
 &= 10(4\cdot 7^{n-1} + 9k).
 \end{align*}

As $4\cdot 7^{n-1} + 9k$ equals an integer, $P(n+1)$ is also true in the case where $n+1$ is odd.
\end{proof}

We now rephrase the theorem and again prove this variant by induction:

\begin{theorem}
For every $n\in\mathbb N_0$ it holds that $7^{2n+1} + 3^{2n+1}$ is divisible by $10$.
\end{theorem}

\begin{proof}
We show this by induction using proposition $P(n)$: ``$7^{2n+1} + 3^{2n+1}$ is divisible by $10$''.
\medskip

\noindent\emph{Base case $n=0$:} From $7^{2\cdot 0 + 1} + 3^{2\cdot 0 + 1} = 10$ we see that $P(0)$ is true.
\smallskip

\noindent\emph{Induction hypothesis:} Suppose $P(k)$ is true for all $0\leq k \leq n$.
\medskip

\noindent\emph{Inductive step: $n \rightarrow n + 1$}:
\smallskip

We need to show that $7^{2(n+1)+1} + 3^{2(n+1)+1}$ is divisible by $10$.

\begin{align*}
7^{2(n+1)+1} + 3^{2(n+1)+1} &= 7^{2n+3} + 3^{2n + 3}\\
    &= 7^27^{2n+1} + 3^23^{2n+1}\\
    &= 49\cdot7^{2n+1} + 9\cdot3^{2n+1}\\
    &= 40\cdot7^{2n+1} + 9\cdot7^{2n+1} + 9\cdot3^{2n+1}\\
    &= 40\cdot7^{2n+1} + 9(7^{2n+1} + 3^{2n+1}) =: (*)
\end{align*}

From the induction hypotheses ($P(n)$ is true), we know that
there is an integer $k$ such that $10k = 7^{2n+1} +  3^{2n+1}$.
With this $k$, it holds that

\begin{align*}
    (*) = 40\cdot7^{2n+1} + 9(7^{2n+1} + 3^{2n+1}) &= 10\cdot 4\cdot 7^{2n+1} + 9\cdot 10k\\
    &=10(4\cdot 7^{2n+1} + 9k)
\end{align*}
As $(4\cdot 7^{2n+1} + 9k)$ equals an integer, we can conclude that $7^{2(n+1)+1} + 3^{2(n+1)+1}$  is divisible by $10$, so $P(n+1)$ is true.
\end{proof}
\end{document}