100 lines
3.5 KiB
TeX
100 lines
3.5 KiB
TeX
% File: 20-01-2022.tex
|
|
% Created: 12:28:35 Thu, 20 Jan 2022 EST
|
|
% Last Change: 12:28:35 Thu, 20 Jan 2022 EST
|
|
%
|
|
\documentclass[letterpaper]{article}
|
|
\usepackage{amsmath}
|
|
\usepackage{graphicx}
|
|
\usepackage{cancel}
|
|
\usepackage{amssymb}
|
|
\usepackage{listings}
|
|
\usepackage[shortlabels]{enumitem}
|
|
\usepackage{soul}
|
|
%\usepackage[smartEllipses,hashEnumerators,hybrid]{markdown}
|
|
\usepackage{geometry}
|
|
\usepackage{dirtytalk}
|
|
\usepackage{mathtools}
|
|
\usepackage{lplfitch}
|
|
|
|
\geometry{portrait, margin=1in}
|
|
|
|
%\begin{minted}[linenos,bgcolor=LightGray]{[language]}
|
|
|
|
\date{03/15/2022}
|
|
\title{%
|
|
Strong Induction\\
|
|
\large MATH--190--01 : Discrete Mathematics for Computing}
|
|
\author{Blizzard MacDougall}
|
|
\begin{document}
|
|
\maketitle
|
|
\pagenumbering{arabic}
|
|
Previously, we talked on mathematical induction.
|
|
Its used when we can't really use mathematical induction isn't really enough.
|
|
In mathematical induction, the inductive step assumes $P(n)$ and use that to
|
|
show that $P(n+1)$ is also true.
|
|
In strong induction, we instead assume $P(k)$, where $base \le k\le n$, and use
|
|
that to prove that $P(n+1)$ is true.\\
|
|
|
|
\section{Proof Example 1}
|
|
|
|
Lets say that every integer greater than $1$ can be written as the product of
|
|
prime numbers.
|
|
The proof follows as such.\\
|
|
|
|
Let $P(n)$ be the predicate "$n$ can be written as a product of primes."
|
|
|
|
Basis step: $P(2)$ is true, since $2$ is, itself, a prime.
|
|
|
|
Inductive step: The inductive hypothesis is that $P(j)$ is true for every $2\le j\le k$.
|
|
That is, for any $j$ between $2$ and $k$, we can write $j$ as the product of prime numbers.
|
|
Now, we have to show that $P(k+1)$.
|
|
Alternatively, we need to show that $k+1$ can be written as the product of primes.
|
|
|
|
There are two cases to consider, when $k+1$ is prime, and when it is composite.
|
|
|
|
Case 1: If $k+1$ is prime, then we're done.
|
|
|
|
Case 2: If $k+1$ is composite, then we can write $k+1=a * b$ where $2\le a \le k+1$, and
|
|
$2\le b \le k+1$. Since $b$ and $a$ are both less than $k$, through the inductive hypothesis
|
|
they can also be written as a product of primes.
|
|
Thus, if $k+1$ is composite, it can be written as a product of primes -- those primes
|
|
in the factorizations of $a$ and $b$.\\
|
|
|
|
\section{Proof Example 2}
|
|
Recall that the Fibonnacci sequence is the recursively defined sequence given by:
|
|
\begin{equation}
|
|
\begin{split}
|
|
a_0=1\\
|
|
a_1=1\\
|
|
a_{k+1}=a_k+a_{k-1}\ for\ k>1
|
|
\end{split}
|
|
\end{equation}
|
|
|
|
The claim to prove is that $a_k\ge (\frac{3}{2})^{k-2}$ for every $k\ge1$\\
|
|
|
|
Let $P(n)$ be the predicate $a_{n}=a_k+a_{n-1}$.
|
|
|
|
Basis Step: $P(1)$ is true, since:
|
|
\begin{equation}
|
|
a_1=1\ge \frac{2}{3}=\left( \frac{3}{2} \right)^{-1}=\left( \frac{3}{2} \right)^{(1-2)}
|
|
\end{equation}
|
|
|
|
Inductive Step: Assume $P(j)$ is true for all $1\le j\le k$. Now we have to show $P(k+1)$ is true.
|
|
That is, that $a_{k+1}\ge\left( \frac{3}{2} \right)^{k-1}$
|
|
By definition, we know that $a_{k+1}=a_k+a_{k-1}$.
|
|
By the inductive hypothesis, we know that $a_k\ge\left( \frac{3}{2} \right)^{k-2}$.
|
|
Additionally, we know that $a_{k-1}\ge\left( \frac{3}{2} \right)^{k-3}$.
|
|
Given this, we can do the following:
|
|
\begin{equation}
|
|
\begin{split}
|
|
a_{k+1}=a_k+a_{k-1}\\
|
|
\ge \left( \frac{3}{2} \right) ^{k-2} + \left( \frac{3}{2} \right) ^{k-2}\\
|
|
=\left(1+\frac{3}{2}\right) \left( \frac{3}{2} \right)^{k-3}\\
|
|
=\frac{5}{2}\left( \frac{3}{2} \right)^{k-3}\\
|
|
\ge \frac{9}{4}\left( \frac{3}{2} \right)^{k-3}\\
|
|
= \frac{3}{2}^2\left( \frac{3}{2} \right)^{k-3}\\
|
|
=\left(\frac{3}{2}\right)^{k-1}
|
|
\end{split}
|
|
\end{equation}
|
|
|
|
\end{document}
|