Transcript Thinking Mathematically by Robert Blitzer

Proofs, Induction and
Recursion
Basic Proof Techniques
Mathematical Induction
Recursive Functions and
Recurrence Relations
Basic Proof Techniques
 Mathematical
proofs all have their basis in
formal logic.
 There are some basic techniques for
proving things, on the basis of different
logical truths.
 Why are proofs really necessary? Because
intuition and guessing don't always work.

n! < n2 for all integers. True for n = 1, n = 2,
and n = 3, but is it really true? How about
n = 4?
Basic Proof Techniques





There are more integers than there are even
integers.
Intuition tells us that this must be true.
But, if you give me an integer, I can come back
with a unique even integer every time!
So there are no more integers than even
integers.
That's why we need to prove things.
Basic Proof Techniques
 Luckily
for you, you will seldom be called
upon to prove anything in this course (or
any other courses at FDU)
 Unluckily for you, you DO need to
understand why proofs work, what they
mean and how they are formulated.
Basic Proof Techniques
 Exhaustive

proof
not usually effective because it is, of course,
exhausting.
• Prove that the set {a, b, c, d} has 16 subsets.
• {}, {a}, {b}, {c}, {d}, {a, b}, {a, c}, {a, d}, {b, c},
{b, d}, {c, d}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d},
{a, b, c, d}
• That's 16. Imagine having to prove that a set with
10 elements has 1024 subsets!
Basic Proof Techniques
 Direct



proof
use basic mechanisms of deduction.
examples are any of the proofs we saw in the
previous weeks' lectures.
Can be very difficult.
Basic Proof Techniques
 Contraposition






instead of proving the statement itself, which
might be hard to do, prove the contrapositive.
Instead of pq, prove q'p'
Example: Prove that in the universe of
integers, if n2 is odd, then n is odd.
Contrapositive: Prove that if n is even, then n2
is even.
Assume that n is even.
n = 2k
n2 = 4k2 = 2(2k2) which, by definition, is even.
Basic Proof Techniques
 Contradiction


Show that if we assume what we want to
prove is false, then we must arrive at a
contradiction.
Show that 2 can not be represented as a
fraction.
• Suppose 2 is represented by the fraction p/q which
is in lowest terms. That is, the greatest common
divisor of p and q is 1 (gcd(p, q) = 1).
• If gcd(p, q) = 1, then gcd(p2, q2) = 1
• But if p/q = 2, then p2/q2 = 2 and so gcd(p2 ,q2) =
2.
Basic Proof Techniques
 Contradiction


Show that if we assume what we want to prove
is false, then we must arrive at a contradiction.
Show that if x + x = x, then x = 0.
• Suppose that x + x = x for some x ≠ 0
• 2x = x, x ≠ 0
• Dividing both sides by x (allowable since x ≠ 0) we
get that 2 = 1.
• Contradiction!
• Therefore if x + x = x, then x = 0.
Basic Proof Techniques
 Contradiction


Show that the set of real numbers is
uncountable (i.e. – that you can not start
listing all the real numbers in such a way that
every real number will eventually appear in
such a list. Such a proof by contradiction is
called Diagonalization.
We will prove this by contradiction and see
why it's called diagonalization.
Basic Proof Techniques
 Contradiction

Suppose we could create a list of real numbers
such that every real number will eventually
appear. It would look like:
 Some
number is missing from this list!!!!
•0
•1
•2
.a00a01a02a03a04a05 …………. a0n ............................
.a10a11a12a13a14a15 …………. a1n ............................
.a20a21a22a23a24a25 …………. a2n ............................
.
.
.
.
Basic Proof Techniques
 Contradiction

Suppose such a list can be made. It would look
like:
 Now,
consider the number
.a00a11a22a33a44a55 …………. ann ............................
•0
•1
•2
.a00a01a02a03a04a05 …………. a0n ............................
.a10a11a12a13a14a15 …………. a1n ............................
.a20a21a22a23a24a25 …………. a2n ............................
.
.
.
.
Basic Proof Techniques
 Contradiction

Now consider the number created by changing
each digit to another digit (for example 0
becomes a 1, 1 becomes a 2. etc.
.a'00a'11a'22a'33a'44a'55 …………. a'nn ..................
where a'nn ≠ ann for all n
Basic Proof Techniques
 Contradiction

.a'00a'11a'22a'33a'44a'55 …………. a'nn ..................
 This
number is not in the list!!!!!
•0
•1
•2
.a00a01a02a03a04a05 …………. a0n ............................
.a10a11a12a13a14a15 …………. a1n ............................
.a20a21a22a23a24a25 …………. a2n ............................
.
.
.
•n
.
.an0an1an2an3an4an5 …………. ann ............................
 Contradiction.
Therefore it can't be done.
Basic Proof Techniques
 Serendipity





In a tennis tournament, players are eliminated
round by round because only the winner goes
to the next round until there is a final round in
which the winner gets the trophy.
If there are n players, prove that there are
exactly n – 1 games played.
Everyone except the champion loses exactly 1
game.
There are n – 1 non-champions.
There are n – 1 games.
Mathematical Induction
 Based
on creating a one to one correspondence
with the integers and showing that it is true for



the basis: Simplest possible case (usually n = 1)
the assumption: assuming it is true for some n ≥ 1
the statement is true.
the induction: and then showing it is true for n + 1,
where n is the number from the basis
Mathematical Induction
Since it is true for the basis it is true for the next
higher number, and then the next higher, and so on.
That is, if the first domino is knocked over, all of
them will fall.
Mathematical Induction
n(n  1 )
 Show that the sum of the first n integers
2
k 1
n
n( n  1)
equals
k

2
k 1
n
For non-mathematicians
 If
you're not a mathematician, an
expression like n
k
2
k 1
might seem a bit scary.
 Let's explain it. It's really not so bad.
For non-mathematicians
 First
of all, the expression
n
k
2
k 1
stands for "add up the squares (k2) of all the
numbers from 1 to n."
 1 + 4 + 9 + 16 + 25 + … + (n – 1)2 + n2
For non-mathematicians
 For
example, the expression
8
k
2
k 1
stands for add up the squares (k2) of all the
numbers from 1 to 8.
 1 + 4 + 9 + 16 + 25 + 36 + 49 + 64
Mathematical Induction
n(n  1 )
 Show that the sum of the first n integers
2
n
k 1
n( n  1)
equals
k

2
k 1
1
1(1  1) 1(2)
k

1

2
2
k 1
 Basis: When n = 1,
n

Hypothesis:
Assume that

Induction: Show that
n1
n( n  1)
k
, for some n  1

2
k 1
n
Mathematical Induction
n1
( n  1)( n  2)
k
, for the n from the hypothesis

2
k 1
n1
n( n  1)
k   k  ( n  1) 
 ( n  1)

2
k 1
k 1
n
n( n  1)  2(n  1) (n  2)(n  1) (n  1)(n  2)



2
2
2
Therefore, since the result is in the proper form
for n + 1, by Mathematical Induction, it is true
for all n > 0.
Mathematical Induction
 Now
I will prove that all marbles in the
world are the same color.

Proof by induction: (on bags containing n
marbles collected at random)
• Basis: For all bags containing 1 marble, clearly all
the marbles in any of these bags is of the same
color, trivially.
• Hypothesis: Assume that for some n, all the
marbles in any bag containing n marbles will be of
the same color.
Mathematical Induction
• Hypothesis: Assume that for some n, all the
marbles in any bag containing n marbles will be of
the same color.
• Induction: I will now show that for any bag
containing n + 1 marbles, all the marbles in the bag
are of the same color.
All Marbles Are The Same Color
remove one of those
same-colored
marbles and put
that first marble
back inall the
n marbles,
same color
bring back that samecolored marble
Consider any bag
containing n + 1
marbles
theabag
now from
has n
remove
marble
themarbles
bag
by the hypothesis, all the
marbles in this bag of n
marbles are the same color
n+1 marbles all the
same color
QED
Weak Induction vs. Strong
Induction
 The
type of inductive proofs we have
seen are often called proof by strong
induction (or the first principle of
induction).
 There is another type of induction
called weak induction (or the second
principle of induction.)
Weak Induction vs. Strong
Induction
 Proof
by weak induction is the same as
proof by strong induction, except that
we change the hypothesis step.
 Instead of assuming the statement true
for some n ≥ the basis value, we assume
the statement true
for all values up to and including that
n ≥ the basis value
Weak Induction
 Prove
that a fence with n posts has
sections for any n ≥ 1.



n–1
Basis: any fence with 1 post has no sections.
any fence with 2 posts has one section.
Hypothesis: Assume that any fence with at most
n posts, for some n ≥ 1.
Induction: Take any fence with n + 1 posts.
Take out one section anywhere. You now have
two fences, one with k posts and the other with
and n – k + 1 posts.
Weak Induction
 Prove
that a fence with n posts has
n – 1 sections for any n ≥ 1.



Induction (continued): Obviously both k
and n – k + 1 are less than n. So one fence
has k – 1 sections and the other has n – k
sections yielding a total of n – 1 sections.
Now restore the missing section. You
have one fence with n – 1 + 1 = n sections.
Therefore the fence with n + 1 posts has n
sections.
QED
Recursion
 Recursive

definitions.
A recursive definition is a definition with two
parts:
• A basis - some simple case.
• A recursive step – where new items are defined in
terms of previous cases.
 Example:



S(1) = 2 (basis)
S(n) = 2S(n – 1) for n ≥ 2
This defines the set {2, 4, 8, 16, 32, …}
Recursion
 The



Fibonacci numbers:
F(1) = 1 and F(2) = 1 (basis)
F(n) = F(n – 2) + F(n – 1) for n > 2
This defines the set {1, 1, 2, 3, 5, 8, 13, 21, …}
 Note
that the previous example could have
been defined by S = {2n | n >= 1}
 The Fibonacci numbers are always defined
recursively.
Recursion
A


binary tree is
a graph that has no nodes (basis)
a graph with a node that points in the left
direction to a binary tree (called the left
subtree) and in the right direction to a binary
tree (called the right subtree).
Recursion
A
well-formed formula (wff) in propositional
logic is


Any statement letter, or one of the contants T
and F (representing true and false.)
If P and Q are wff's, then so are (P Q), (P  Q),
(P → Q), (P ↔ Q), and (P').
Recursion
 Recursively

defined operations:
For example, exponentiation, an, can be defined
as
• a0 = 1
• an = an – 1, for n ≥ 1
Recursion and Algorithms
 We
often find it more convenient to
define things recursively because it is
easier to develop algorithms for such
objects by using recursive algorithms.
 Consider the earlier definition of a
binary tree. How do we compute the
number of nodes in a given binary
tree?
Recursion and Algorithms
 if
(T.is_empty()) // (no nodes)
T.node_count() = 0;
else
T.node_count() =
T.left_subtree().node_count()
+ T.left_subtree().node_count;
Recursion and Mathematical
Induction
 Recursive
definitions lend themselves
to proof by Mathematical Induction.
 Prove that the Fibonacci number
F(n) < 2n for n ≥ 1.



Basis: consider when n = 1. F(1) = 1,
which is clearly less than 21 = 2.
Hypothesis: assume that F(k) < 2k for all
values less than n some n ≥ 1.
Note that we will be using weak
induction.
Recursion and Mathematical
Induction






Induction: Consider now F(n + 1) where
n is the number from the hypothesis.
We know that F(n + 1) = F(n) + F(n – 1).
But by the hypothesis F(n) < 2n and
F(n-1) < 2n-1.
So F(n + 1) < 2n + 2n-1.
But 2n + 2n-1 < 2n + 2n which is equal to
22n which in turn is equal to 2n+1.
So F(n + 1) < 2n+1.
QED