Discrete Mathematics-mathematical Induction

Applied Discrete Mathematics Mathematical Induction William Shoaff

Spring 2008

Outline

1

Introduction to Induction

Outline

1

Introduction to Induction

2

Induction on Sequences

Outline

1

Introduction to Induction

2

Induction on Sequences

3

Induction on Sums

Quotation

The concept of “mathematical induction” should be distinguished from what is usually called “inductive reasoning” in science. – Don Knuth “The Art of Computer Programming: Fundamental Algorithms” American computer scientist (1938 – )

Mathematical Induction

Mathematical Induction

Inductive reasoning is a logic used for discovery in science

Mathematical Induction

Inductive reasoning is a logic used for discovery in science Repeated observation of consistent results leads to a conjecture

Mathematical Induction

Inductive reasoning is a logic used for discovery in science Repeated observation of consistent results leads to a conjecture

The principle of mathematical induction is an axiom in the theory of natural numbers

Mathematical Induction

Inductive reasoning is a logic used for discovery in science Repeated observation of consistent results leads to a conjecture

The principle of mathematical induction is an axiom in the theory of natural numbers Mathematical induction is a template procedure used to establish facts about enumerable sets

Mathematical Induction

Inductive reasoning is a logic used for discovery in science Repeated observation of consistent results leads to a conjecture

The principle of mathematical induction is an axiom in the theory of natural numbers Mathematical induction is a template procedure used to establish facts about enumerable sets There is a basis for induction, an observation of the fact in some instance

Mathematical Induction

Inductive reasoning is a logic used for discovery in science Repeated observation of consistent results leads to a conjecture

The principle of mathematical induction is an axiom in the theory of natural numbers Mathematical induction is a template procedure used to establish facts about enumerable sets There is a basis for induction, an observation of the fact in some instance And there is a material implication that “if the fact is true in some instance, then it will be true in the next instance”

Observations: Full Binary Trees

Observations: Full Binary Trees

The full binary tree of height h = 0 has 1 node

Observations: Full Binary Trees

The full binary tree of height h = 0 has 1 node The full binary tree of height h = 1 has 3 nodes 1

2

3

Observations: Full Binary Trees

Observations: Full Binary Trees

The full binary tree of height h = 2 has 7 nodes 1

2

4

3

5

6

7

Question

Question

What is the functional relationship between the height h of a full binary tree and the number of nodes n in the tree?

Question

What is the functional relationship between the height h of a full binary tree and the number of nodes n in the tree?

Question

What is the functional relationship between the height h of a full binary tree and the number of nodes n in the tree? Observations Height Nodes h=0 n=1 h=1 n=3 h=2 n=7

Hypothesis

Hypothesis

The full binary tree of height h has n = 2h+1 − 1 nodes

Hypothesis

The full binary tree of height h has n = 2h+1 − 1 nodes This statement is true for h = 0, 1 and 2

Hypothesis

The full binary tree of height h has n = 2h+1 − 1 nodes This statement is true for h = 0, 1 and 2

Hypothesis

The full binary tree of height h has n = 2h+1 − 1 nodes This statement is true for h = 0, 1 and 2 Height 0 1 2

Nodes 1 = 2(0+1) − 1 3 = 2(1+1) − 1 7 = 2(2+1) − 1

To prove the statement for every integer

Hypothesis

The full binary tree of height h has n = 2h+1 − 1 nodes This statement is true for h = 0, 1 and 2 Height 0 1 2

Nodes 1 = 2(0+1) − 1 3 = 2(1+1) − 1 7 = 2(2+1) − 1

To prove the statement for every integer show that if it is true for some height h ≥ 0, then it will be true for height h + 1

Height h, Full Binary Tree Has 2h+1 − 1 Nodes

Height h, Full Binary Tree Has 2h+1 − 1 Nodes

A full binary tree of height h + 1 is constructed from

Height h, Full Binary Tree Has 2h+1 − 1 Nodes

A full binary tree of height h + 1 is constructed from 1 root node

root

Height h, Full Binary Tree Has 2h+1 − 1 Nodes

A full binary tree of height h + 1 is constructed from 1 root node A full left subtree of of height h

root

left subtree

Height h, Full Binary Tree Has 2h+1 − 1 Nodes

A full binary tree of height h + 1 is constructed from 1 root node A full left subtree of of height h A full right subtree of of height h

root

left subtree

right subtree

Height h, Full Binary Tree Has 2h+1 − 1 Nodes

A full binary tree of height h + 1 is constructed from 1 root node A full left subtree of of height h A full right subtree of of height h

root

left subtree

right subtree

height h

Height h, Full Binary Tree Has 2h+1 − 1 Nodes

A full binary tree of height h + 1 is constructed from 1 root node A full left subtree of of height h A full right subtree of of height h

root height 1

left subtree

right subtree

height h

Height h, Full Binary Tree Has 2h+1 − 1 Nodes root height 1 left subtree

right subtree

height h

Height h, Full Binary Tree Has 2h+1 − 1 Nodes root height 1 left subtree

right subtree

height h

If the left and right subtree both have 2h+1 − 1 nodes,

Height h, Full Binary Tree Has 2h+1 − 1 Nodes root height 1 left subtree

right subtree

height h

If the left and right subtree both have 2h+1 − 1 nodes,

Height h, Full Binary Tree Has 2h+1 − 1 Nodes root height 1 left subtree

right subtree

height h

If the left and right subtree both have 2h+1 − 1 nodes, then the nodes in the higher tree are

Height h, Full Binary Tree Has 2h+1 − 1 Nodes root height 1 left subtree

right subtree

height h

If the left and right subtree both have 2h+1 − 1 nodes, then the nodes in the higher tree are (1 root node) + (nodes in left) + (nodes in right)

Height h, Full Binary Tree Has 2h+1 − 1 Nodes root height 1 left subtree

right subtree

height h

If the left and right subtree both have 2h+1 − 1 nodes, then the nodes in the higher tree are (1 root node) + (nodes in left) + (nodes in right)

Height h, Full Binary Tree Has 2h+1 − 1 Nodes root height 1 left subtree

right subtree

height h

If the left and right subtree both have 2h+1 − 1 nodes, then the nodes in the higher tree are (1 root node) + (nodes in left) + (nodes in right) 1 + (2h − 1) + (2h+1 − 1)

Height h, Full Binary Tree Has 2h+1 − 1 Nodes root height 1 left subtree

right subtree

height h

If the left and right subtree both have 2h+1 − 1 nodes, then the nodes in the higher tree are (1 root node) + (nodes in left) + (nodes in right) 1 + (2h − 1) + (2h+1 − 1) = 1 + 2(2h+1 − 1)

Height h, Full Binary Tree Has 2h+1 − 1 Nodes root height 1 left subtree

right subtree

height h

If the left and right subtree both have 2h+1 − 1 nodes, then the nodes in the higher tree are (1 root node) + (nodes in left) + (nodes in right) 1 + (2h − 1) + (2h+1 − 1) = 1 + 2(2h+1 − 1) = 1 + (2h+2 − 2)

Height h, Full Binary Tree Has 2h+1 − 1 Nodes root height 1 left subtree

right subtree

height h

If the left and right subtree both have 2h+1 − 1 nodes, then the nodes in the higher tree are (1 root node) + (nodes in left) + (nodes in right) 1 + (2h − 1) + (2h+1 − 1) = 1 + 2(2h+1 − 1) = 1 + (2h+2 − 2) = 2h+2 − 1

Gauss Fools the Third Grade Teacher

Gauss Fools the Third Grade Teacher

There is an often told story, with many variations, of how young Gauss irritated his third grade teacher

Gauss Fools the Third Grade Teacher

There is an often told story, with many variations, of how young Gauss irritated his third grade teacher The class was asked to compute the value of the sum 1 + 2 + 3 + · · · + 99 + 100

Gauss Fools the Third Grade Teacher

There is an often told story, with many variations, of how young Gauss irritated his third grade teacher The class was asked to compute the value of the sum 1 + 2 + 3 + · · · + 99 + 100 Almost immediately Gauss answered 5050

Gauss Fools the Third Grade Teacher

There is an often told story, with many variations, of how young Gauss irritated his third grade teacher The class was asked to compute the value of the sum 1 + 2 + 3 + · · · + 99 + 100 Almost immediately Gauss answered 5050 Perhaps Gauss knew the total would be the number of terms (100) times the average of the first and last term   1 + 100 1 + 2 + 3 + · · · + 99 + 100 = 100 = 50(101) = 5050 2

Generalizing the Problem

Generalizing the Problem

Consider the more general sum 0 + 1 + 2 + 3 + · · · + (n − 2) + (n − 1)

Generalizing the Problem

Consider the more general sum 0 + 1 + 2 + 3 + · · · + (n − 2) + (n − 1) The sum has n terms

Generalizing the Problem

Consider the more general sum 0 + 1 + 2 + 3 + · · · + (n − 2) + (n − 1) The sum has n terms The first term is 0, the last term is (n − 1), and their average is (n − 1)/2

Generalizing the Problem

Consider the more general sum 0 + 1 + 2 + 3 + · · · + (n − 2) + (n − 1) The sum has n terms The first term is 0, the last term is (n − 1), and their average is (n − 1)/2 Is it true that  0 + 1 + 2 + 3 + · · · + (n − 2) + (n − 1) = n

 n−1 ? 2

Prove

P

k=

n(n−1) 2

Prove

P

k=

n(n−1) 2

To prove  0 + 1 + 2 + 3 + · · · + (n − 2) + (n − 1) = n is true for all natural numbers n, show

n−1 2



Prove

P

k=

n(n−1) 2

To prove  0 + 1 + 2 + 3 + · · · + (n − 2) + (n − 1) = n is true for all natural numbers n, show Basis: For n = 0

n−1 2



Prove

P

k=

n(n−1) 2

To prove  0 + 1 + 2 + 3 + · · · + (n − 2) + (n − 1) = n

n−1 2



is true for all natural numbers n, show Basis: For n = 0 The sum on the left is empty, and so equal to 0 0 + 1 + · · · + (0 − 2) + (0 − 1) = 0 (empty sum)

Prove

P

k=

n(n−1) 2

To prove  0 + 1 + 2 + 3 + · · · + (n − 2) + (n − 1) = n

n−1 2



is true for all natural numbers n, show Basis: For n = 0 The sum on the left is empty, and so equal to 0 0 + 1 + · · · + (0 − 2) + (0 − 1) = 0 (empty sum) The right hand side is also equal to 0 for n = 0   0−1 0 =0 2

Prove

P

k=

n(n−1) 2

Prove

P

k=

n(n−1) 2

Prove

P

k=

Induction:

n(n−1) 2

Pretend 0 + 1 + 2 + · · · + (n − 2) + (n − 1) = for some n ≥ 0

n(n − 1) 2

Prove

P

k=

Induction:

n(n−1) 2

Pretend 0 + 1 + 2 + · · · + (n − 2) + (n − 1) = for some n ≥ 0 Then the next sum is:

n(n − 1) 2

Prove

P

k=

Induction:

n(n−1) 2

Pretend 0 + 1 + 2 + · · · + (n − 2) + (n − 1) = for some n ≥ 0 Then the next sum is:

n(n − 1) 2

Prove

P

k=

Induction:

n(n−1) 2

Pretend 0 + 1 + 2 + · · · + (n − 2) + (n − 1) = for some n ≥ 0 Then the next sum is: [0 + 1 + · · · + (n − 1)] + n

n(n − 1) 2

Prove

P

k=

Induction:

n(n−1) 2

Pretend 0 + 1 + 2 + · · · + (n − 2) + (n − 1) =

n(n − 1) 2

for some n ≥ 0 Then the next sum is: [0 + 1 + · · · + (n − 1)] + n =

n(n − 1) +n 2

Prove

P

k=

Induction:

n(n−1) 2

Pretend 0 + 1 + 2 + · · · + (n − 2) + (n − 1) =

n(n − 1) 2

for some n ≥ 0 Then the next sum is: n(n − 1) +n 2 n(n − 1) 2n = + 2 2

[0 + 1 + · · · + (n − 1)] + n =

Prove

P

k=

Induction:

n(n−1) 2

Pretend 0 + 1 + 2 + · · · + (n − 2) + (n − 1) =

n(n − 1) 2

for some n ≥ 0 Then the next sum is: n(n − 1) +n 2 n(n − 1) 2n = + 2 2 n(n + 1) = 2

[0 + 1 + · · · + (n − 1)] + n =

Which shows the next sum equals the function at the next natural number

Inductive Template For Functional Equality

Inductive Template For Functional Equality

To prove “f (n) = g (n)” is true for all natural numbers n

Inductive Template For Functional Equality

To prove “f (n) = g (n)” is true for all natural numbers n Basis: Show: both functions map 0 to the same value, that is, f (0) = g (0)

Inductive Template For Functional Equality

To prove “f (n) = g (n)” is true for all natural numbers n Basis: Show: both functions map 0 to the same value, that is, f (0) = g (0) Induction: Show: if f (n) = g (n) for some n ≥ 0, then f (n + 1) = g (n + 1)

Quotation

The so-called law of induction cannot possibly be a law of logic, since it is obviously a proposition with a sense. Nor, therefore, can it be an a priori law. Ludwig Wittenstein, "Tractatus Logico-Philosophicus" Austrian-British philosoper (1889 - 1951)

Checking Solutions to Algebraic Equations

Checking Solutions to Algebraic Equations

Pretend you want to check that x = 4 is a solution to the linear equation 3x − 5 = 7

Checking Solutions to Algebraic Equations

Pretend you want to check that x = 4 is a solution to the linear equation 3x − 5 = 7 You can do this by substitiuting 4 for x on the left-hand side and show the result is the right-hand side 3(4) − 5 = 12 − 5 = 7

Checking Solutions to Algebraic Equations

Checking Solutions to Algebraic Equations Pretend you want to check that x = (1 + to the quadratic equation x2 = x + 1

√

5)/2 is a solution

Checking Solutions to Algebraic Equations Pretend you want to check that x = (1 + to the quadratic equation

√

5)/2 is a solution

x2 = x + 1 √ You can do this by substitiuting (1 + 5)/2 for x in both the left-hand and right-hand sides and show the results are equal

Checking Solutions to Algebraic Equations Pretend you want to check that x = (1 + to the quadratic equation

√

5)/2 is a solution

x2 = x + 1 √ You can do this by substitiuting (1 + 5)/2 for x in both the left-hand and right-hand sides and show the results are equal The left-hand side is √ !2 √ √ 1+ 5 1+2 5+5 3+ 5 = = 2 4 2

Checking Solutions to Algebraic Equations Pretend you want to check that x = (1 + to the quadratic equation

√

5)/2 is a solution

x2 = x + 1 √ You can do this by substitiuting (1 + 5)/2 for x in both the left-hand and right-hand sides and show the results are equal The left-hand side is √ !2 √ √ 1+ 5 1+2 5+5 3+ 5 = = 2 4 2 The right-hand side is √ √ √ 1+ 5 2 3+ 5 1+ 5 +1= + = 2 2 2 2

Checking Solutions to Recurrence Equations

Checking Solutions to Recurrence Equations The same basic idea can be used to check a proposed solution to a recurrence equation

Checking Solutions to Recurrence Equations The same basic idea can be used to check a proposed solution to a recurrence equation Suppose you want to show that mn = 2n − 1 is a solution to the recurrence mn = 2mn−1 + 1

Checking Solutions to Recurrence Equations The same basic idea can be used to check a proposed solution to a recurrence equation Suppose you want to show that mn = 2n − 1 is a solution to the recurrence mn = 2mn−1 + 1 You can do this by substitiuting 2n − 1 for mn in the left-hand side and 2n−1 − 1 for mn−1 in the right-hand sides and show the results are equal

Checking Solutions to Recurrence Equations The same basic idea can be used to check a proposed solution to a recurrence equation Suppose you want to show that mn = 2n − 1 is a solution to the recurrence mn = 2mn−1 + 1 You can do this by substitiuting 2n − 1 for mn in the left-hand side and 2n−1 − 1 for mn−1 in the right-hand sides and show the results are equal The left-hand side is 2n − 1

Checking Solutions to Recurrence Equations The same basic idea can be used to check a proposed solution to a recurrence equation Suppose you want to show that mn = 2n − 1 is a solution to the recurrence mn = 2mn−1 + 1 You can do this by substitiuting 2n − 1 for mn in the left-hand side and 2n−1 − 1 for mn−1 in the right-hand sides and show the results are equal The left-hand side is 2n − 1 The right-hand side is
2 2n−1 − 1 + 1 = (2n − 2) + 1 = 2n − 1

Checking Solutions to Recurrence Equations

Checking Solutions to Recurrence Equations There’s is one problem with this

Checking Solutions to Recurrence Equations There’s is one problem with this For any constant c, you can show mn = c2n − 1 is a solution to the recurrence mn = 2mn−1 + 1

Checking Solutions to Recurrence Equations There’s is one problem with this For any constant c, you can show mn = c2n − 1 is a solution to the recurrence mn = 2mn−1 + 1 The left-hand side would be c2n − 1

Checking Solutions to Recurrence Equations There’s is one problem with this For any constant c, you can show mn = c2n − 1 is a solution to the recurrence mn = 2mn−1 + 1 The left-hand side would be c2n − 1 And the right-hand side would be
2 c2n−1 − 1 + 1 = c2n − 1

Checking Solutions to Recurrence Equations There’s is one problem with this For any constant c, you can show mn = c2n − 1 is a solution to the recurrence mn = 2mn−1 + 1 The left-hand side would be c2n − 1 And the right-hand side would be
2 c2n−1 − 1 + 1 = c2n − 1

An initial value nails down the solution: If m0 = 0, then c20 − 1 = c − 1 = 0 forces c to be 1

Induction on The Triangular Sequence

Induction on The Triangular Sequence Consider the recurrence for the triangular numbers tn = tn−1 + (n − 1)

Induction on The Triangular Sequence Consider the recurrence for the triangular numbers tn = tn−1 + (n − 1) To show that tn = n(n − 1)/2 solves the recurrence substitute into the left-hand and right hand sides

Induction on The Triangular Sequence Consider the recurrence for the triangular numbers tn = tn−1 + (n − 1) To show that tn = n(n − 1)/2 solves the recurrence substitute into the left-hand and right hand sides The left-hand side is n(n − 1)/2

Induction on The Triangular Sequence Consider the recurrence for the triangular numbers tn = tn−1 + (n − 1) To show that tn = n(n − 1)/2 solves the recurrence substitute into the left-hand and right hand sides The left-hand side is n(n − 1)/2 The right-hand side is (n − 1)(n − 2) (n − 1)(n − 2) 2(n − 1) + (n − 1) = + 2 2 2 (n − 1)(n − 2) + 2(n − 1) = 2 n(n − 1) = 2

Induction on The Triangular Sequence Consider the recurrence for the triangular numbers tn = tn−1 + (n − 1) To show that tn = n(n − 1)/2 solves the recurrence substitute into the left-hand and right hand sides The left-hand side is n(n − 1)/2 The right-hand side is (n − 1)(n − 2) (n − 1)(n − 2) 2(n − 1) + (n − 1) = + 2 2 2 (n − 1)(n − 2) + 2(n − 1) = 2 n(n − 1) = 2

To complete the induction, establish the basis: t0 = 0(0 − 1)/2 = 0

Induction on The Mersenne Sequence

Induction on The Mersenne Sequence Consider the recurrence for the Mersenne numbers mn = 2mn−1 + 1 or, relabeling subscripts mn+1 = 2mn + 1

Induction on The Mersenne Sequence Consider the recurrence for the Mersenne numbers mn = 2mn−1 + 1 or, relabeling subscripts mn+1 = 2mn + 1 If mn = 2n − 1, then mn+1 = 2mn + 1 = 2(2n − 1) + 1

Induction on The Mersenne Sequence Consider the recurrence for the Mersenne numbers mn = 2mn−1 + 1 or, relabeling subscripts mn+1 = 2mn + 1 If mn = 2n − 1, then mn+1 = 2mn + 1 = 2(2n − 1) + 1 Which can be rewritten as mn+1 = 2n+1 − 1

Induction on The Mersenne Sequence Consider the recurrence for the Mersenne numbers mn = 2mn−1 + 1 or, relabeling subscripts mn+1 = 2mn + 1 If mn = 2n − 1, then mn+1 = 2mn + 1 = 2(2n − 1) + 1 Which can be rewritten as mn+1 = 2n+1 − 1 The function 2n − 1 maps 0 to 0 which matches the initial Mersenne number m0 = 0

Induction on The Mersenne Sequence Consider the recurrence for the Mersenne numbers mn = 2mn−1 + 1 or, relabeling subscripts mn+1 = 2mn + 1 If mn = 2n − 1, then mn+1 = 2mn + 1 = 2(2n − 1) + 1 Which can be rewritten as mn+1 = 2n+1 − 1 The function 2n − 1 maps 0 to 0 which matches the initial Mersenne number m0 = 0 Since both the basis and the inductive conditional are both true, the Mersenne numbers mn can be computed by the function m(n) = 2n − 1 for all natural numbers n

Induction on The Fermat Sequence

Induction on The Fermat Sequence Consider the recurrence for the Fermat numbers rn = (rn−1 − 1)2 + 1 or, relabeling subscripts rn+1 = (rn − 1)2 + 1

Induction on The Fermat Sequence Consider the recurrence for the Fermat numbers rn = (rn−1 − 1)2 + 1 or, relabeling subscripts rn+1 = (rn − 1)2 + 1 n

If rn = 22 + 1, then n

rn+1 = ((22 + 1) − 1)2 + 1

Induction on The Fermat Sequence Consider the recurrence for the Fermat numbers rn = (rn−1 − 1)2 + 1 or, relabeling subscripts rn+1 = (rn − 1)2 + 1 n

If rn = 22 + 1, then n

rn+1 = ((22 + 1) − 1)2 + 1 Which can be rewritten as rn+1 = 22

n+1

+1

Induction on The Fermat Sequence Consider the recurrence for the Fermat numbers rn = (rn−1 − 1)2 + 1 or, relabeling subscripts rn+1 = (rn − 1)2 + 1 n

If rn = 22 + 1, then n

rn+1 = ((22 + 1) − 1)2 + 1 Which can be rewritten as rn+1 = 22 n

n+1

+1

The function 22 + 1 maps 0 to 3 which matches the initial Fermat number r0 = 3

Induction on The Fermat Sequence Consider the recurrence for the Fermat numbers rn = (rn−1 − 1)2 + 1 or, relabeling subscripts rn+1 = (rn − 1)2 + 1 n

If rn = 22 + 1, then n

rn+1 = ((22 + 1) − 1)2 + 1 Which can be rewritten as rn+1 = 22 n

n+1

+1

The function 22 + 1 maps 0 to 3 which matches the initial Fermat number r0 = 3 Since both the basis and the inductive conditional are both true, the Fermat numbers rn can be computed by the function n r (n) = 22 + 1 for all natural numbers n

Quotation

MacPherson told me that my theorem can be viewed as blah blah blah Grothendick blah blah blah, which makes it much more respectable. I think some intuition leaks out in every step of an induction proof. Jim Propp, American mathematician

Induction on Sums

Induction on Sums P To prove a summation ak can be expressed as a function g (·) on the natural numbers,

Induction on Sums P To prove a summation ak can be expressed as a function g (·) on the natural numbers, Establish a basis for induction, that is, show 0 X k=0

ak = a0 = g (0)

Induction on Sums P To prove a summation ak can be expressed as a function g (·) on the natural numbers, Establish a basis for induction, that is, show 0 X

ak = a0 = g (0)

k=0

Prove the inductive conditional: If If

n−1 X k=0

then

ak = g (n),

Induction on Sums P To prove a summation ak can be expressed as a function g (·) on the natural numbers, Establish a basis for induction, that is, show 0 X

ak = a0 = g (0)

k=0

Prove the inductive conditional: If If

n−1 X k=0

then

ak = g (n),

Induction on Sums P To prove a summation ak can be expressed as a function g (·) on the natural numbers, Establish a basis for induction, that is, show 0 X

ak = a0 = g (0)

k=0

Prove the inductive conditional: If If

n−1 X k=0

then n X k=0

ak

ak = g (n),

Induction on Sums P To prove a summation ak can be expressed as a function g (·) on the natural numbers, Establish a basis for induction, that is, show 0 X

ak = a0 = g (0)

k=0

Prove the inductive conditional: If If

n−1 X

ak = g (n),

k=0

then n X k=0

ak =

"n−1 X k=0

# ak + an

Induction on Sums P To prove a summation ak can be expressed as a function g (·) on the natural numbers, Establish a basis for induction, that is, show 0 X

ak = a0 = g (0)

k=0

Prove the inductive conditional: If If

n−1 X

ak = g (n),

k=0

then n X k=0

ak =

"n−1 X

# ak + an

k=0

= g (n) + an

Induction on Sums P To prove a summation ak can be expressed as a function g (·) on the natural numbers, Establish a basis for induction, that is, show 0 X

ak = a0 = g (0)

k=0

Prove the inductive conditional: If If

n−1 X

ak = g (n),

k=0

then n X k=0

ak =

"n−1 X

# ak + an

k=0

= g (n) + an = g (n + 1)

Alice Sum Math Induction Proof

Alice Sum Math Induction Proof

The Alice sum formula n−1 X

1=n

k=0

can be established by mathematical induction

Alice Sum Math Induction Proof

The Alice sum formula n−1 X

1=n

k=0

can be established by mathematical induction Basis: For n = 0

Alice Sum Math Induction Proof

The Alice sum formula n−1 X

1=n

k=0

can be established by mathematical induction Basis: For n = 0 The sum

n−1 X

1=

k=0

is empty and equal to 0

0−1 X k=0

1

Alice Sum Math Induction Proof

The Alice sum formula n−1 X

1=n

k=0

can be established by mathematical induction Basis: For n = 0 The sum

n−1 X k=0

1=

0−1 X

1

k=0

is empty and equal to 0 The value on the right hand, n, is 0 too

Alice Sum Math Induction Proof

Alice Sum Math Induction Proof Induction: Show that

Alice Sum Math Induction Proof Induction: Show that If

n−1 X

1 = n,

k=0

then

n X k=0

By computing

1=n+1

Alice Sum Math Induction Proof Induction: Show that If

n−1 X

1 = n,

k=0

then

n X k=0

By computing

1=n+1

Alice Sum Math Induction Proof Induction: Show that If

n−1 X

1 = n,

k=0

then

n X k=0

By computing n X k=0

1

1=n+1

Alice Sum Math Induction Proof Induction: Show that If

n−1 X

1 = n,

k=0

then

n X

1=n+1

k=0

By computing n X k=0

"n−1 # X 1= 1 +1 k=0

Alice Sum Math Induction Proof Induction: Show that If

n−1 X

1 = n,

k=0

then

n X

1=n+1

k=0

By computing n X k=0

"n−1 # X 1= 1 +1 k=0

=n+1

Gauss Sum Math Induction Proof

Gauss Sum Math Induction Proof The Gauss sum formula n−1 X

k = 0 + 1 + 2 + 3 + · · · + (n − 1) =

k=0

can be established by mathematical induction

n(n − 1) 2

Gauss Sum Math Induction Proof The Gauss sum formula n−1 X

k = 0 + 1 + 2 + 3 + · · · + (n − 1) =

k=0

n(n − 1) 2

can be established by mathematical induction Basis: For n = 0 the sum on the left is empty, and so equal to 0. And the right hand side is 0(0 − 1)/2 = 0 too

Gauss Sum Math Induction Proof The Gauss sum formula n−1 X

k = 0 + 1 + 2 + 3 + · · · + (n − 1) =

k=0

n(n − 1) 2

can be established by mathematical induction Basis: For n = 0 the sum on the left is empty, and so equal to 0. And the right hand side is 0(0 − 1)/2 = 0 too P Induction: If n−1 k=0 k = n(n − 1)/2, then n X k=0

"n−1 # X k= k + n = (n + 1)n/2 k=0

Zeno Sum Math Induction Proof

Zeno Sum Math Induction Proof The Zeno sum formula n−1 X

2k = 1 + 2 + 4 + · · · + 2n−1 = 2n − 1

k=0

can be established by mathematical induction

Zeno Sum Math Induction Proof The Zeno sum formula n−1 X

2k = 1 + 2 + 4 + · · · + 2n−1 = 2n − 1

k=0

can be established by mathematical induction Basis: For n = 0 the sum on the left is empty, and so equal to 0. And the right hand side n is 0 too

Zeno Sum Math Induction Proof The Zeno sum formula n−1 X

2k = 1 + 2 + 4 + · · · + 2n−1 = 2n − 1

k=0

can be established by mathematical induction Basis: For n = 0 the sum on the left is empty, and so equal to 0. And the right hand side n is 0 too P k n Induction: If n−1 k=0 2 = 2 − 1, then n X k=0

k

2 =

"n−1 X k=0

# 2

k

+ 2n = 2n+1 − 1

Sum of the Odd Integers is a Square

Sum of the Odd Integers is a Square

The ancient formula n X

(2k − 1) = 1 + 3 + 5 + · · · + (2n − 1) = n2

k=1

can be established by mathematical induction

Sum of the Odd Integers is a Square

The ancient formula n X

(2k − 1) = 1 + 3 + 5 + · · · + (2n − 1) = n2

k=1

can be established by mathematical induction Basis: For n = 0 the sum on the left is empty, and so equal to 0. And the right hand side n is 0 too.

Sum of the Odd Integers is a Square

n X k=1

(2k − 1) = 1 + 3 + 5 + · · · + (2n − 1) = n2

Sum of the Odd Integers is a Square

n X

(2k − 1) = 1 + 3 + 5 + · · · + (2n − 1) = n2

k=1

Induction: If

Pn

k=1 (2k

− 1) = n2 , then

Sum of the Odd Integers is a Square

n X

(2k − 1) = 1 + 3 + 5 + · · · + (2n − 1) = n2

k=1

Induction: If

Pn

k=1 (2k

− 1) = n2 , then

Sum of the Odd Integers is a Square

n X

(2k − 1) = 1 + 3 + 5 + · · · + (2n − 1) = n2

k=1

Induction: If

Pn

k=1 (2k

n+1 X k=1

− 1) = n2 , then

(2k − 1)

Sum of the Odd Integers is a Square

n X

(2k − 1) = 1 + 3 + 5 + · · · + (2n − 1) = n2

k=1

Induction: If

Pn

k=1 (2k

n+1 X k=1

− 1) = n2 , then

# n X (2k − 1) + 2(n + 1) − 1 (2k − 1) = "

k=1

Sum of the Odd Integers is a Square

n X

(2k − 1) = 1 + 3 + 5 + · · · + (2n − 1) = n2

k=1

Induction: If

Pn

k=1 (2k

n+1 X k=1

− 1) = n2 , then

# n X (2k − 1) + 2(n + 1) − 1 (2k − 1) = "

k=1 2

= n + 2(n + 1) − 1

Sum of the Odd Integers is a Square

n X

(2k − 1) = 1 + 3 + 5 + · · · + (2n − 1) = n2

k=1

Induction: If

Pn

k=1 (2k

n+1 X k=1

− 1) = n2 , then

# n X (2k − 1) + 2(n + 1) − 1 (2k − 1) = "

k=1 2

= n + 2(n + 1) − 1 = n2 + 2n + 1

Sum of the Odd Integers is a Square

n X

(2k − 1) = 1 + 3 + 5 + · · · + (2n − 1) = n2

k=1

Induction: If

Pn

k=1 (2k

n+1 X k=1

− 1) = n2 , then

# n X (2k − 1) + 2(n + 1) − 1 (2k − 1) = "

k=1 2

= n + 2(n + 1) − 1 = n2 + 2n + 1 = (n + 1)2

Sum of Cubes is a Squared Triangular Number

Sum of Cubes is a Squared Triangular Number

The formula

n−1 X k=1

3

k =



2 1 n(n − 1) 2

can be established by mathematical induction

Sum of Cubes is a Squared Triangular Number

The formula

n−1 X k=1

3

k =



2 1 n(n − 1) 2

can be established by mathematical induction Basis: For n = 0 the sum on the left is empty, and so equal to 0. And the right hand side n is 0 too.

Sum of Cubes is a Squared Triangular Number n−1 X k=1

3

k =



2 1 n(n − 1) 2

Sum of Cubes is a Squared Triangular Number n−1 X k=1

Induction: If

Pn−1

k=1 k

3

3

k =



2 1 n(n − 1) 2

= n2 (n − 1)2 /4, then

Sum of Cubes is a Squared Triangular Number n−1 X k=1

Induction: If

Pn−1

k=1 k

3

3

k =



2 1 n(n − 1) 2

= n2 (n − 1)2 /4, then

Sum of Cubes is a Squared Triangular Number n−1 X

3



k =

k=1

Induction: If

Pn−1

k=1 k

3

2 1 n(n − 1) 2

= n2 (n − 1)2 /4, then n X k=1

k3

Sum of Cubes is a Squared Triangular Number n−1 X

3

k =

k=1

Induction: If

Pn−1

k=1 k

3



2 1 n(n − 1) 2

= n2 (n − 1)2 /4, then "n−1 # n X X 3 k = k 3 + n3 k=1

k=1

Sum of Cubes is a Squared Triangular Number n−1 X

3

k =

k=1

Induction: If

Pn−1

k=1 k

3



2 1 n(n − 1) 2

= n2 (n − 1)2 /4, then "n−1 # n X X 3 k = k 3 + n3 k=1

k=1

 =

1 n(n − 1) 2

2

+ n3

Sum of Cubes is a Squared Triangular Number n−1 X

3

k =

k=1

Induction: If

Pn−1

k=1 k

3



2 1 n(n − 1) 2

= n2 (n − 1)2 /4, then "n−1 # n X X 3 k = k 3 + n3 k=1

k=1

2 1 n(n − 1) + n3 2   2 2 (n − 1) =n +n 4 

=

Sum of Cubes is a Squared Triangular Number n−1 X

3

k =

k=1

Induction: If

Pn−1

k=1 k

3



2 1 n(n − 1) 2

= n2 (n − 1)2 /4, then "n−1 # n X X 3 k = k 3 + n3 k=1

k=1

2 1 n(n − 1) + n3 2   2 2 (n − 1) =n +n 4   2 (n + 2n + 1) =n 4 

=

Sum of Cubes is a Squared Triangular Number n−1 X

3

k =

k=1

Induction: If

Pn−1

k=1 k

3



2 1 n(n − 1) 2

= n2 (n − 1)2 /4, then "n−1 # n X X 3 k = k 3 + n3 k=1

k=1

2 1 n(n − 1) + n3 2   2 2 (n − 1) =n +n 4   2 (n + 2n + 1) =n 4  2 1 = n(n + 1) 2 

=

Sum of Fibonacci Numbers

Sum of Fibonacci Numbers

Recall the Fibonacci sequence ~ = h0, 1, 1, 2, 3, 5, 8, 13, 21, . . .i F

Sum of Fibonacci Numbers

Recall the Fibonacci sequence ~ = h0, 1, 1, 2, 3, 5, 8, 13, 21, . . .i F Also recall the recurrence for the Fibonacci numbers fn = fn−1 + fn−2 ,

n ∈ {2, 3, 4, . . .},

f0 = 0, f1 = 1

Sum of Fibonacci Numbers

Recall the Fibonacci sequence ~ = h0, 1, 1, 2, 3, 5, 8, 13, 21, . . .i F Also recall the recurrence for the Fibonacci numbers fn = fn−1 + fn−2 ,

n ∈ {2, 3, 4, . . .},

f0 = 0, f1 = 1

Let’s write the sequence using the names of the numbers rather than their values ~ = hf0 , f1 , f2 , f3 , f4 , f5 , f6 , f7 , f8 , . . .i F

Sum of Fibonacci Numbers ~ = h0, 1, 1, 2, 3, 5, 8, 13, 21, . . .i F ~ = hf0 , f1 , f2 , f3 , f4 , f5 , f6 , f7 , f8 , . . .i F

Sum of Fibonacci Numbers ~ = h0, 1, 1, 2, 3, 5, 8, 13, 21, . . .i F ~ = hf0 , f1 , f2 , f3 , f4 , f5 , f6 , f7 , f8 , . . .i F Consider the sequence of partial sums

Sum of Fibonacci Numbers ~ = h0, 1, 1, 2, 3, 5, 8, 13, 21, . . .i F ~ = hf0 , f1 , f2 , f3 , f4 , f5 , f6 , f7 , f8 , . . .i F Consider the sequence of partial sums

Sum of Fibonacci Numbers ~ = h0, 1, 1, 2, 3, 5, 8, 13, 21, . . .i F ~ = hf0 , f1 , f2 , f3 , f4 , f5 , f6 , f7 , f8 , . . .i F Consider the sequence of partial sums S0

Sum of Fibonacci Numbers ~ = h0, 1, 1, 2, 3, 5, 8, 13, 21, . . .i F ~ = hf0 , f1 , f2 , f3 , f4 , f5 , f6 , f7 , f8 , . . .i F Consider the sequence of partial sums S0 = f0 = 0

Sum of Fibonacci Numbers ~ = h0, 1, 1, 2, 3, 5, 8, 13, 21, . . .i F ~ = hf0 , f1 , f2 , f3 , f4 , f5 , f6 , f7 , f8 , . . .i F Consider the sequence of partial sums S0 = f0 = 0 S1

Sum of Fibonacci Numbers ~ = h0, 1, 1, 2, 3, 5, 8, 13, 21, . . .i F ~ = hf0 , f1 , f2 , f3 , f4 , f5 , f6 , f7 , f8 , . . .i F Consider the sequence of partial sums S0 = f0 = 0 S1 = f0 + f1 = 1

Sum of Fibonacci Numbers ~ = h0, 1, 1, 2, 3, 5, 8, 13, 21, . . .i F ~ = hf0 , f1 , f2 , f3 , f4 , f5 , f6 , f7 , f8 , . . .i F Consider the sequence of partial sums S0 = f0 = 0 S1 = f0 + f1 = 1 S2

Sum of Fibonacci Numbers ~ = h0, 1, 1, 2, 3, 5, 8, 13, 21, . . .i F ~ = hf0 , f1 , f2 , f3 , f4 , f5 , f6 , f7 , f8 , . . .i F Consider the sequence of partial sums S0 = f0 = 0 S1 = f0 + f1 = 1 S2 = f0 + f1 + f2 = 2

Sum of Fibonacci Numbers ~ = h0, 1, 1, 2, 3, 5, 8, 13, 21, . . .i F ~ = hf0 , f1 , f2 , f3 , f4 , f5 , f6 , f7 , f8 , . . .i F Consider the sequence of partial sums S0 = f0 = 0 S1 = f0 + f1 = 1 S2 = f0 + f1 + f2 = 2 S3

Sum of Fibonacci Numbers ~ = h0, 1, 1, 2, 3, 5, 8, 13, 21, . . .i F ~ = hf0 , f1 , f2 , f3 , f4 , f5 , f6 , f7 , f8 , . . .i F Consider the sequence of partial sums S0 = f0 = 0 S1 = f0 + f1 = 1 S2 = f0 + f1 + f2 = 2 S3 = f0 + f1 + f2 + f3 = 4

Sum of Fibonacci Numbers ~ = h0, 1, 1, 2, 3, 5, 8, 13, 21, . . .i F ~ = hf0 , f1 , f2 , f3 , f4 , f5 , f6 , f7 , f8 , . . .i F Consider the sequence of partial sums S0 = f0 = 0 S1 = f0 + f1 = 1 S2 = f0 + f1 + f2 = 2 S3 = f0 + f1 + f2 + f3 = 4 S4

Sum of Fibonacci Numbers ~ = h0, 1, 1, 2, 3, 5, 8, 13, 21, . . .i F ~ = hf0 , f1 , f2 , f3 , f4 , f5 , f6 , f7 , f8 , . . .i F Consider the sequence of partial sums S0 = f0 = 0 S1 = f0 + f1 = 1 S2 = f0 + f1 + f2 = 2 S3 = f0 + f1 + f2 + f3 = 4 S4 = f0 + f1 + f2 + f3 + f4 = 7

Sum of Fibonacci Numbers ~ = h0, 1, 1, 2, 3, 5, 8, 13, 21, . . .i F ~ = hf0 , f1 , f2 , f3 , f4 , f5 , f6 , f7 , f8 , . . .i F Consider the sequence of partial sums S0 = f0 = 0 S1 = f0 + f1 = 1 S2 = f0 + f1 + f2 = 2 S3 = f0 + f1 + f2 + f3 = 4 S4 = f0 + f1 + f2 + f3 + f4 = 7 S4

Sum of Fibonacci Numbers ~ = h0, 1, 1, 2, 3, 5, 8, 13, 21, . . .i F ~ = hf0 , f1 , f2 , f3 , f4 , f5 , f6 , f7 , f8 , . . .i F Consider the sequence of partial sums S0 = f0 = 0 S1 = f0 + f1 = 1 S2 = f0 + f1 + f2 = 2 S3 = f0 + f1 + f2 + f3 = 4 S4 = f0 + f1 + f2 + f3 + f4 = 7 S4 = f0 + f1 + f2 + f3 + f4 + f5 = 12 Can you make a conjecture about these sums?

Sum of Fibonacci Numbers

n−1 X k=0

fk = fn+1 − 1

Sum of Fibonacci Numbers

n−1 X k=0

Basis: For n = 0

fk = fn+1 − 1

Sum of Fibonacci Numbers

n−1 X

fk = fn+1 − 1

k=0

Basis: For n = 0 The sum on the left-hand side is empty and so equal to 0

Sum of Fibonacci Numbers

n−1 X

fk = fn+1 − 1

k=0

Basis: For n = 0 The sum on the left-hand side is empty and so equal to 0 The formula on the right-hand side is also equal to 0 f0+1 − 1 = f1 − 1 = 1 − 1 = 0

Sum of Fibonacci Numbers

n−1 X

fk = fn+1 − 1

k=0

Basis: For n = 0 The sum on the left-hand side is empty and so equal to 0 The formula on the right-hand side is also equal to 0 f0+1 − 1 = f1 − 1 = 1 − 1 = 0 This establishes the basis for induction

Sum of Fibonacci Numbers n−1 X k=0

fk = fn+1 − 1

Sum of Fibonacci Numbers n−1 X

fk = fn+1 − 1

k=0

Induction: Pretend that

n−1 X k=0

is true for some n ≥ 0

fk = fn+1 − 1

Sum of Fibonacci Numbers n−1 X

fk = fn+1 − 1

k=0

Induction: Pretend that

n−1 X k=0

is true for some n ≥ 0 Then

fk = fn+1 − 1

Sum of Fibonacci Numbers n−1 X

fk = fn+1 − 1

k=0

Induction: Pretend that

n−1 X k=0

is true for some n ≥ 0 Then

fk = fn+1 − 1

Sum of Fibonacci Numbers n−1 X

fk = fn+1 − 1

k=0

Induction: Pretend that

n−1 X

fk = fn+1 − 1

k=0

is true for some n ≥ 0 Then n X fk k=0

Sum of Fibonacci Numbers n−1 X

fk = fn+1 − 1

k=0

Induction: Pretend that

n−1 X

fk = fn+1 − 1

k=0

is true for some n ≥ 0 Then "n−1 # n X X fk + fn fk = k=0

k=1

Sum of Fibonacci Numbers n−1 X

fk = fn+1 − 1

k=0

Induction: Pretend that

n−1 X

fk = fn+1 − 1

k=0

is true for some n ≥ 0 Then "n−1 # n X X fk + fn fk = k=0

k=1

= [fn+1 − 1] + fn

Sum of Fibonacci Numbers n−1 X

fk = fn+1 − 1

k=0

Induction: Pretend that

n−1 X

fk = fn+1 − 1

k=0

is true for some n ≥ 0 Then "n−1 # n X X fk + fn fk = k=0

k=1

= [fn+1 − 1] + fn = [fn+1 + fn ] − 1

Sum of Fibonacci Numbers n−1 X

fk = fn+1 − 1

k=0

Induction: Pretend that

n−1 X

fk = fn+1 − 1

k=0

is true for some n ≥ 0 Then "n−1 # n X X fk + fn fk = k=0

k=1

= [fn+1 − 1] + fn = [fn+1 + fn ] − 1 = fn+2 − 1

Pascal’s Triangle

Pascal’s Triangle

1 1 1 1 1 1 1 1 1 .. .

1 2 3 4 5 6 7 8 .. .

1 3 6 10 15 21 28 .. .

1 4 1 10 5 1 20 15 6 1 35 35 21 7 1 56 70 56 28 8 1 .. .. .. .. .. .. . . . . . . . . .

Pascal’s Triangle: Sum of Rows

Pascal’s Triangle: Sum of Rows

There are many identities that can be found in Pascal’s triangle

Pascal’s Triangle: Sum of Rows

There are many identities that can be found in Pascal’s triangle Perhaps the most famous one is found by summing values in a row

Pascal’s Triangle: Sum of Rows

There are many identities that can be found in Pascal’s triangle Perhaps the most famous one is found by summing values in a row

Pascal’s Triangle: Sum of Rows

There are many identities that can be found in Pascal’s triangle Perhaps the most famous one is found by summing values in a row 1

Pascal’s Triangle: Sum of Rows

There are many identities that can be found in Pascal’s triangle Perhaps the most famous one is found by summing values in a row 1

=1

Pascal’s Triangle: Sum of Rows

There are many identities that can be found in Pascal’s triangle Perhaps the most famous one is found by summing values in a row 1 1 +1

=1

Pascal’s Triangle: Sum of Rows

There are many identities that can be found in Pascal’s triangle Perhaps the most famous one is found by summing values in a row 1 1 +1

=1 =2

Pascal’s Triangle: Sum of Rows

There are many identities that can be found in Pascal’s triangle Perhaps the most famous one is found by summing values in a row 1 1 +1 1 +2

=1 =2 +1

Pascal’s Triangle: Sum of Rows

There are many identities that can be found in Pascal’s triangle Perhaps the most famous one is found by summing values in a row 1 1 +1 1 +2

+1

=1 =2 =4

Pascal’s Triangle: Sum of Rows

There are many identities that can be found in Pascal’s triangle Perhaps the most famous one is found by summing values in a row 1 1 +1 1 +2 1 +3

+1 +3

=1 =2 =4 +1

Pascal’s Triangle: Sum of Rows

There are many identities that can be found in Pascal’s triangle Perhaps the most famous one is found by summing values in a row 1 1 +1 1 +2 1 +3

+1 +3

+1

=1 =2 =4 =8

Pascal’s Triangle: Sum of Rows

There are many identities that can be found in Pascal’s triangle Perhaps the most famous one is found by summing values in a row 1 1 1 1 1

+1 +2 +3 +4

+1 +3 +6

+1 +4

=1 =2 =4 =8 +1

Pascal’s Triangle: Sum of Rows

There are many identities that can be found in Pascal’s triangle Perhaps the most famous one is found by summing values in a row 1 1 1 1 1

+1 +2 +3 +4

+1 +3 +6

+1 +4

+1

=1 =2 =4 =8 = 16

Pascal’s Triangle: Sum of Rows

There are many identities that can be found in Pascal’s triangle Perhaps the most famous one is found by summing values in a row 1 1 1 1 1 1

+1 +2 +1 +3 +3 +1 +4 +6 +4 +5 +10 +10

+1 +5

=1 =2 =4 =8 = 16 +1

Pascal’s Triangle: Sum of Rows

There are many identities that can be found in Pascal’s triangle Perhaps the most famous one is found by summing values in a row 1 1 1 1 1 1

+1 +2 +1 +3 +3 +1 +4 +6 +4 +5 +10 +10

+1 +5

+1

=1 =2 =4 =8 = 16 = 32

Pascal’s Triangle: Sum of Rows

There are many identities that can be found in Pascal’s triangle Perhaps the most famous one is found by summing values in a row 1 1 1 1 1 1 1

=1 +1 =2 +2 +1 =4 +3 +3 +1 =8 +4 +6 +4 +1 = 16 +5 +10 +10 +5 +1 = 32 +6 +15 +20 +15 +6 +1

Pascal’s Triangle: Sum of Rows

There are many identities that can be found in Pascal’s triangle Perhaps the most famous one is found by summing values in a row 1 1 1 1 1 1 1

=1 +1 =2 +2 +1 =4 +3 +3 +1 =8 +4 +6 +4 +1 = 16 +5 +10 +10 +5 +1 = 32 +6 +15 +20 +15 +6 +1 = 64

Pascal’s Triangle: Sum of Rows

Pascal’s Triangle: Sum of Rows

We can make the conjecture

Pascal’s Triangle: Sum of Rows

We can make the conjecture The sum of values in row n of Pascal’s triangle is 2n for n = 0, 1, 2, 3, . . .

Pascal’s Triangle: Sum of Rows

We can make the conjecture The sum of values in row n of Pascal’s triangle is 2n for n = 0, 1, 2, 3, . . .

When you notice how a row is computed from the previous row, it becomes clear why the row sums double

Pascal’s Triangle: Sum of Rows

We can make the conjecture The sum of values in row n of Pascal’s triangle is 2n for n = 0, 1, 2, 3, . . .

When you notice how a row is computed from the previous row, it becomes clear why the row sums double Every term, except the first and last 1, is added twice to generate the next row

Pascal’s Triangle: Sum of Rows

Pascal’s Triangle: Sum of Rows Consider row 6 of Pascal’s Triangle 1 6 15 20 15 6 1

Pascal’s Triangle: Sum of Rows Consider row 6 of Pascal’s Triangle 1 6 15 20 15 6 1 It can be used to generate row 7 1 7 21 35 35 21 7 1

Pascal’s Triangle: Sum of Rows Consider row 6 of Pascal’s Triangle 1 6 15 20 15 6 1 It can be used to generate row 7 1 7 21 35 35 21 7 1 Sum adjacent numbers in row 6 yields

Pascal’s Triangle: Sum of Rows Consider row 6 of Pascal’s Triangle 1 6 15 20 15 6 1 It can be used to generate row 7 1 7 21 35 35 21 7 1 Sum adjacent numbers in row 6 yields 1+6

Pascal’s Triangle: Sum of Rows Consider row 6 of Pascal’s Triangle 1 6 15 20 15 6 1 It can be used to generate row 7 1 7 21 35 35 21 7 1 Sum adjacent numbers in row 6 yields 1+6 7

Pascal’s Triangle: Sum of Rows Consider row 6 of Pascal’s Triangle 1 6 15 20 15 6 1 It can be used to generate row 7 1 7 21 35 35 21 7 1 Sum adjacent numbers in row 6 yields 1 + 6 6 + 15 7

Pascal’s Triangle: Sum of Rows Consider row 6 of Pascal’s Triangle 1 6 15 20 15 6 1 It can be used to generate row 7 1 7 21 35 35 21 7 1 Sum adjacent numbers in row 6 yields 1 + 6 6 + 15 7

21

Pascal’s Triangle: Sum of Rows Consider row 6 of Pascal’s Triangle 1 6 15 20 15 6 1 It can be used to generate row 7 1 7 21 35 35 21 7 1 Sum adjacent numbers in row 6 yields 1 + 6 6 + 15 15 + 20 7

21

Pascal’s Triangle: Sum of Rows Consider row 6 of Pascal’s Triangle 1 6 15 20 15 6 1 It can be used to generate row 7 1 7 21 35 35 21 7 1 Sum adjacent numbers in row 6 yields 1 + 6 6 + 15 15 + 20 7

21

35

Pascal’s Triangle: Sum of Rows Consider row 6 of Pascal’s Triangle 1 6 15 20 15 6 1 It can be used to generate row 7 1 7 21 35 35 21 7 1 Sum adjacent numbers in row 6 yields 1 + 6 6 + 15 15 + 20 20 + 15 7

21

35

Pascal’s Triangle: Sum of Rows Consider row 6 of Pascal’s Triangle 1 6 15 20 15 6 1 It can be used to generate row 7 1 7 21 35 35 21 7 1 Sum adjacent numbers in row 6 yields 1 + 6 6 + 15 15 + 20 20 + 15 7

21

35

35

Pascal’s Triangle: Sum of Rows Consider row 6 of Pascal’s Triangle 1 6 15 20 15 6 1 It can be used to generate row 7 1 7 21 35 35 21 7 1 Sum adjacent numbers in row 6 yields 1 + 6 6 + 15 15 + 20 20 + 15 15 + 6 7

21

35

35

Pascal’s Triangle: Sum of Rows Consider row 6 of Pascal’s Triangle 1 6 15 20 15 6 1 It can be used to generate row 7 1 7 21 35 35 21 7 1 Sum adjacent numbers in row 6 yields 1 + 6 6 + 15 15 + 20 20 + 15 15 + 6 7

21

35

35

21

Pascal’s Triangle: Sum of Rows Consider row 6 of Pascal’s Triangle 1 6 15 20 15 6 1 It can be used to generate row 7 1 7 21 35 35 21 7 1 Sum adjacent numbers in row 6 yields 1 + 6 6 + 15 15 + 20 20 + 15 15 + 6 6 + 1 7

21

35

35

21

Pascal’s Triangle: Sum of Rows Consider row 6 of Pascal’s Triangle 1 6 15 20 15 6 1 It can be used to generate row 7 1 7 21 35 35 21 7 1 Sum adjacent numbers in row 6 yields 1 + 6 6 + 15 15 + 20 20 + 15 15 + 6 6 + 1 7

21

35

35

21

7

Pascal’s Triangle: Sum of Rows Consider row 6 of Pascal’s Triangle 1 6 15 20 15 6 1 It can be used to generate row 7 1 7 21 35 35 21 7 1 Sum adjacent numbers in row 6 yields 1 + 6 6 + 15 15 + 20 20 + 15 15 + 6 6 + 1 7

21

35

35

21

7

Adding in the initial and terminal 1 in row 7 shows each term in row 6 is summed twice when summing row 7

Pascal’s Triangle: Sum of Rows Consider row 6 of Pascal’s Triangle 1 6 15 20 15 6 1 It can be used to generate row 7 1 7 21 35 35 21 7 1 Sum adjacent numbers in row 6 yields 1 1 + 6 6 + 15 15 + 20 20 + 15 15 + 6 6 + 1 1 1

7

21

35

35

21

7 1

Adding in the initial and terminal 1 in row 7 shows each term in row 6 is summed twice when summing row 7

Pascal’s Triangle: Sum of Rows

Pascal’s Triangle: Sum of Rows To make the preceding argument precise we must name things

Pascal’s Triangle: Sum of Rows To make the preceding argument precise we must name things We’ll name the rows and columns by the natural numbers

Pascal’s Triangle: Sum of Rows To make the preceding argument precise we must name things We’ll name the rows and columns by the natural numbers

Pascal’s Triangle: Sum of Rows To make the preceding argument precise we must name things We’ll name the rows and columns by the natural numbers

0 1 2 3 4 5 6 7 8 .. .

0 1 1 1 1 1 1 1 1 1 .. .

1

2

3

4

5

6

7

8

1 2 3 4 5 6 7 8 .. .

1 3 6 10 15 21 28 .. .

1 4 1 10 5 1 20 15 6 1 35 35 21 7 1 56 70 56 28 8 1 .. .. .. .. .. . . . . . . . .

···

Pascal’s Triangle: Binomial Coefficients

Pascal’s Triangle: Binomial Coefficients

We’ll name terms in row n, column m by the symbol

n m




Pascal’s Triangle: Binomial Coefficients

We’ll name terms in row n, column m by the symbol
n The symbol m is called a binomial coefficient

n m




Pascal’s Triangle: Binomial Coefficients

We’ll name terms in row n, column m by the symbol
n The symbol m is called a binomial coefficient
n The symbol m is read “n choose m”

n m




Pascal’s Triangle: Binomial Coefficients

We’ll name terms in row n, column m by the symbol
n The symbol m is called a binomial coefficient
n The symbol m is read “n choose m”

n m




The binomial coefficient “n choose m” can be expressed in terms of factorials   n n! = m m!(n − m)!

Pascal’s Triangle

Pascal’s Triangle

0 1 2 3 4 5 6 7 8 .. .

0
0 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0

.. .

1

2

3

4

5

6

7

8

1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1

2 2
3 2
4 2
5 2
6 2
7 2
8 2

3 3
4 3
5 3
6 3
7 3
8 3

4 4
5 4
6 4
7 4
8 4

5 5
6 5
7 5
8 5

6 6
7 6
8 6

7 7
8 7

8 8

···




.. .




.. .




.. .




.. .




.. .




.. .




.. .

..


.

Pascal’s Identity

Pascal’s Identity

The relationship between terms in row n − 1 and row n is called Pascal’s identity

Pascal’s Identity

The relationship between terms in row n − 1 and row n is called Pascal’s identity Pascal’s identity states that       n−1 n−1 n + = m−1 m m

Pascal’s Identity

The relationship between terms in row n − 1 and row n is called Pascal’s identity Pascal’s identity states that       n−1 n−1 n + = m−1 m m That is, the sum of terms in columns m − 1 and m of row n − 1 equals the term in column m row n

Pascal’s Identity

Pascal’s Identity

An example of Pascal’s identity is   7 7! 7×6×5 = = = 35 4 4!3! 3×2×1 and

Therefore

  7 7! 7×6 = = = 21 5 5!2! 2×1       8 7 7 = + = 35 + 21 5 4 5

Pascal’s Identity

Pascal’s Identity

Another example of Pascal’s identity is   12 12! = = 495 8 8!4! and

Therefore

  12 12! = = 660 9 9!3!   13 = 495 + 660 = 1155 9

Pascal’s Triangle Row Sum

Pascal’s Triangle Row Sum Armed with Pascal’s identity, we can use induction to establish the sum of values in row n is 2n

Pascal’s Triangle Row Sum Armed with Pascal’s identity, we can use induction to establish the sum of values in row n is 2n To sum the elements in row n we write           n   X n n n n n n = + + + ··· + + k 0 1 2 n−1 n k=0

Pascal’s Triangle Row Sum Armed with Pascal’s identity, we can use induction to establish the sum of values in row n is 2n To sum the elements in row n we write           n   X n n n n n n = + + + ··· + + k 0 1 2 n−1 n k=0

Leave the first and last terms alone, but use Pascal’s identity on the middle terms           n n−1 n−1 n−1 n−1 + + + + 0 0 1 1 2       n−1 n−1 n + ··· + + + n−2 n−1 n

Pascal’s Triangle Row Sum

Pascal’s Triangle Row Sum

Collect the terms that appear twice             n n−1 n−1 n−1 n−1 n + +2 +· · ·+2 + + 0 0 1 n−2 n−1 n

Pascal’s Triangle Row Sum

Collect the terms that appear twice             n n−1 n−1 n−1 n−1 n + +2 +· · ·+2 + + 0 0 1 n−2 n−1 n Recognize that the first two and last two terms are equal to 1 and so can be replaced as         n−1 n−1 n−1 n−1 2 +2 + ··· + 2 +2 0 1 n−2 n−1

Pascal’s Triangle Row Sum

Collect the terms that appear twice             n n−1 n−1 n−1 n−1 n + +2 +· · ·+2 + + 0 0 1 n−2 n−1 n Recognize that the first two and last two terms are equal to 1 and so can be replaced as         n−1 n−1 n−1 n−1 2 +2 + ··· + 2 +2 0 1 n−2 n−1 Therefore, if the sum of terms in row n − 1 is 2n−1 , the sum of terms in row n is 2n

Epigraph

φ is an H of a lot cooler than π. Stettner, in Dan Brown’s “The Da Vinci Code”

Cassini’s Identity

Theorem (Cassini’s Identity) Fn+1 Fn−1 − Fn2 = (−1)n ,

for n > 0

Cassini’s Identity

Theorem (Cassini’s Identity) Fn+1 Fn−1 − Fn2 = (−1)n ,

for n > 0

Interpret Cassini’s identity as stating the area of a rectangle with sides Fn−1 and Fn+1 is plus or minus one the area of a square with sides Fn

Cassini’s Identity

Theorem (Cassini’s Identity) Fn+1 Fn−1 − Fn2 = (−1)n ,

for n > 0

Interpret Cassini’s identity as stating the area of a rectangle with sides Fn−1 and Fn+1 is plus or minus one the area of a square with sides Fn Arithmetically, multiply every other Fibonacci number and subtract the square of the number in the middle

Cassini’s Identity

Theorem (Cassini’s Identity) Fn+1 Fn−1 − Fn2 = (−1)n ,

for n > 0

Interpret Cassini’s identity as stating the area of a rectangle with sides Fn−1 and Fn+1 is plus or minus one the area of a square with sides Fn Arithmetically, multiply every other Fibonacci number and subtract the square of the number in the middle The result alternates between −1 and +1

Cassini’s Identity

Cassini’s Identity

n 0 1 2 3 4 5 6 7 8 9 ... Fn 0 1 1 2 3 5 8 13 21 34 . . .

Cassini’s Identity

n 0 1 2 3 4 5 6 7 8 9 ... Fn 0 1 1 2 3 5 8 13 21 34 . . . 0 · 1 − 12

Cassini’s Identity

n 0 1 2 3 4 5 6 7 8 9 ... Fn 0 1 1 2 3 5 8 13 21 34 . . . 0 · 1 − 12 = −1

Cassini’s Identity

n 0 1 2 3 4 5 6 7 8 9 ... Fn 0 1 1 2 3 5 8 13 21 34 . . . 0 · 1 − 12 = −1 2 · 1 − 12

Cassini’s Identity

n 0 1 2 3 4 5 6 7 8 9 ... Fn 0 1 1 2 3 5 8 13 21 34 . . . 0 · 1 − 12 = −1 2 · 1 − 12 = 1

Cassini’s Identity

n 0 1 2 3 4 5 6 7 8 9 ... Fn 0 1 1 2 3 5 8 13 21 34 . . . 0 · 1 − 12 = −1 2 · 1 − 12 = 1 3 · 1 − 22

Cassini’s Identity

n 0 1 2 3 4 5 6 7 8 9 ... Fn 0 1 1 2 3 5 8 13 21 34 . . . 0 · 1 − 12 = −1 2 · 1 − 12 = 1 3 · 1 − 22 = −1

Cassini’s Identity

n 0 1 2 3 4 5 6 7 8 9 ... Fn 0 1 1 2 3 5 8 13 21 34 . . . 0 · 1 − 12 = −1 2 · 1 − 12 = 1 3 · 1 − 22 = −1 5 · 2 − 32

Cassini’s Identity

n 0 1 2 3 4 5 6 7 8 9 ... Fn 0 1 1 2 3 5 8 13 21 34 . . . 0 · 1 − 12 = −1 2 · 1 − 12 = 1 3 · 1 − 22 = −1 5 · 2 − 32 = 1

Cassini’s Identity

n 0 1 2 3 4 5 6 7 8 9 ... Fn 0 1 1 2 3 5 8 13 21 34 . . . 0 · 1 − 12 = −1 2 · 1 − 12 = 1 3 · 1 − 22 = −1 5 · 2 − 32 = 1 8 · 3 − 52

Cassini’s Identity

n 0 1 2 3 4 5 6 7 8 9 ... Fn 0 1 1 2 3 5 8 13 21 34 . . . 0 · 1 − 12 = −1 2 · 1 − 12 = 1 3 · 1 − 22 = −1 5 · 2 − 32 = 1 8 · 3 − 52 = −1

Lewis Carroll’s Favorite Trick

Cassini’s identity is the basis of an absurdity attributed Lewis Carroll

Lewis Carroll’s Favorite Trick

Cassini’s identity is the basis of an absurdity attributed Lewis Carroll Cut the 8 × 8 square along the lines indicated below and arrange the pieces into a 5 × 13 rectangle to conclude that 64 = 65.

Inductive Proof of Cassini’s Identity Fn+1 Fn−1 − Fn2 = (−1)n ,

for n > 0

Replace Fn−1 by Fn+1 − Fn in the left-hand side of Cassini’s proposed identity to obtain

Inductive Proof of Cassini’s Identity Fn+1 Fn−1 − Fn2 = (−1)n ,

for n > 0

Replace Fn−1 by Fn+1 − Fn in the left-hand side of Cassini’s proposed identity to obtain

Inductive Proof of Cassini’s Identity Fn+1 Fn−1 − Fn2 = (−1)n ,

for n > 0

Replace Fn−1 by Fn+1 − Fn in the left-hand side of Cassini’s proposed identity to obtain Fn+1 Fn−1 − Fn2

Inductive Proof of Cassini’s Identity Fn+1 Fn−1 − Fn2 = (−1)n ,

for n > 0

Replace Fn−1 by Fn+1 − Fn in the left-hand side of Cassini’s proposed identity to obtain Fn+1 Fn−1 − Fn2 = Fn+1 (Fn+1 − Fn ) − Fn2

Inductive Proof of Cassini’s Identity Fn+1 Fn−1 − Fn2 = (−1)n ,

for n > 0

Replace Fn−1 by Fn+1 − Fn in the left-hand side of Cassini’s proposed identity to obtain Fn+1 Fn−1 − Fn2 = Fn+1 (Fn+1 − Fn ) − Fn2 2 = Fn+1 − Fn+1 Fn − Fn2

Inductive Proof of Cassini’s Identity Fn+1 Fn−1 − Fn2 = (−1)n ,

for n > 0

Replace Fn−1 by Fn+1 − Fn in the left-hand side of Cassini’s proposed identity to obtain Fn+1 Fn−1 − Fn2 = Fn+1 (Fn+1 − Fn ) − Fn2 2 = Fn+1 − Fn+1 Fn − Fn2 2 = Fn+1 − Fn (Fn+1 + Fn )

Inductive Proof of Cassini’s Identity Fn+1 Fn−1 − Fn2 = (−1)n ,

for n > 0

Replace Fn−1 by Fn+1 − Fn in the left-hand side of Cassini’s proposed identity to obtain Fn+1 Fn−1 − Fn2 = Fn+1 (Fn+1 − Fn ) − Fn2 2 = Fn+1 − Fn+1 Fn − Fn2 2 = Fn+1 − Fn (Fn+1 + Fn ) 2 = Fn+1 − Fn Fn+2

Inductive Proof of Cassini’s Identity Fn+1 Fn−1 − Fn2 = (−1)n ,

for n > 0

Replace Fn−1 by Fn+1 − Fn in the left-hand side of Cassini’s proposed identity to obtain Fn+1 Fn−1 − Fn2 = Fn+1 (Fn+1 − Fn ) − Fn2 2 = Fn+1 − Fn+1 Fn − Fn2 2 = Fn+1 − Fn (Fn+1 + Fn ) 2 = Fn+1 − Fn Fn+2 2 = −(Fn Fn+2 − Fn+1 )

Inductive Proof of Cassini’s Identity Fn+1 Fn−1 − Fn2 = (−1)n ,

for n > 0

Replace Fn−1 by Fn+1 − Fn in the left-hand side of Cassini’s proposed identity to obtain Fn+1 Fn−1 − Fn2 = Fn+1 (Fn+1 − Fn ) − Fn2 2 = Fn+1 − Fn+1 Fn − Fn2 2 = Fn+1 − Fn (Fn+1 + Fn ) 2 = Fn+1 − Fn Fn+2 2 = −(Fn Fn+2 − Fn+1 ) 2 = −(Fn+2 Fn − Fn+1 )

Inductive Proof of Cassini’s Identity

Fn+1 Fn−1 − Fn2 = (−1)n ,

for n > 0

Thus if Fn+1 Fn−1 − Fn2 = (−1)n

Inductive Proof of Cassini’s Identity

Fn+1 Fn−1 − Fn2 = (−1)n ,

for n > 0

Thus if Fn+1 Fn−1 − Fn2 = (−1)n Then 2 Fn+2 Fn − Fn+1 = (−1)n+1

Inductive Proof of Cassini’s Identity

Fn+1 Fn−1 − Fn2 = (−1)n ,

for n > 0

Thus if Fn+1 Fn−1 − Fn2 = (−1)n Then 2 Fn+2 Fn − Fn+1 = (−1)n+1

Since F2 F0 − F1 = 1 · 0 − 1 = (−1)1 , the basis for induction is true, so Cassini’s identity holds for all n.

Fundamental Theorem of Arithmetic

The fundamental theorem of arithmetic states that every positive integer greater than 1 can be written as a (unique) product of primes

Fundamental Theorem of Arithmetic

The fundamental theorem of arithmetic states that every positive integer greater than 1 can be written as a (unique) product of primes As a basis 2 is prime, hence a product of primes

Fundamental Theorem of Arithmetic

The fundamental theorem of arithmetic states that every positive integer greater than 1 can be written as a (unique) product of primes As a basis 2 is prime, hence a product of primes Pretend that for some n ≥ 2, every integer k = 2, 3, . . . , n can be written as the product of primes

Fundamental Theorem of Arithmetic

The fundamental theorem of arithmetic states that every positive integer greater than 1 can be written as a (unique) product of primes As a basis 2 is prime, hence a product of primes Pretend that for some n ≥ 2, every integer k = 2, 3, . . . , n can be written as the product of primes Consider n + 1

Fundamental Theorem of Arithmetic

The fundamental theorem of arithmetic states that every positive integer greater than 1 can be written as a (unique) product of primes As a basis 2 is prime, hence a product of primes Pretend that for some n ≥ 2, every integer k = 2, 3, . . . , n can be written as the product of primes Consider n + 1 If n + 1 is prime, then it is the product of primes

Fundamental Theorem of Arithmetic

The fundamental theorem of arithmetic states that every positive integer greater than 1 can be written as a (unique) product of primes As a basis 2 is prime, hence a product of primes Pretend that for some n ≥ 2, every integer k = 2, 3, . . . , n can be written as the product of primes Consider n + 1 If n + 1 is prime, then it is the product of primes If n + 1 is composite, then n + 1 = ab where 1 < a < n + 1 and 1 < b < n + 1

Fundamental Theorem of Arithmetic

The fundamental theorem of arithmetic states that every positive integer greater than 1 can be written as a (unique) product of primes As a basis 2 is prime, hence a product of primes Pretend that for some n ≥ 2, every integer k = 2, 3, . . . , n can be written as the product of primes Consider n + 1 If n + 1 is prime, then it is the product of primes If n + 1 is composite, then n + 1 = ab where 1 < a < n + 1 and 1 < b < n + 1 Therefore, by the inductive assumption, a and b are the product of primes, and so n + 1 is the product of primes

The Fundamental Theorem of the Sum and Difference Calculus

Define the falling factorial power nm by nm = n(n − 1) · · · (n − m + 1)

The Fundamental Theorem of the Sum and Difference Calculus

Define the falling factorial power nm by nm = n(n − 1) · · · (n − m + 1) The following identity is true m

n−1 X k=0

k m−1 m =

n−1 X k=0

k(k − 1) · · · (k − m + 2) = nm

The Fundamental Theorem of the Sum and Difference Calculus

Define the falling factorial power nm by nm = n(n − 1) · · · (n − m + 1) The following identity is true m

n−1 X k=0

k m−1 m =

n−1 X

k(k − 1) · · · (k − m + 2) = nm

k=0

As a basis for induction, when n = 0 the left-hand side equals the right-hand side

The Fundamental Theorem of the Sum and Difference Calculus Pretend m

n−1 X k=0

is true for some n ≥ 0

k m−1 = nm

The Fundamental Theorem of the Sum and Difference Calculus Pretend m

n−1 X k=0

is true for some n ≥ 0 Then

k m−1 = nm

The Fundamental Theorem of the Sum and Difference Calculus Pretend m

n−1 X k=0

is true for some n ≥ 0 Then

k m−1 = nm

The Fundamental Theorem of the Sum and Difference Calculus Pretend m

n−1 X k=0

is true for some n ≥ 0 Then n X m k m−1 k=0

k m−1 = nm

The Fundamental Theorem of the Sum and Difference Calculus Pretend m

n−1 X

k m−1 = nm

k=0

is true for some n ≥ 0 Then n n−1 X X m−1 m k =m k m−1 + mnm−1 k=0

k=0

The Fundamental Theorem of the Sum and Difference Calculus Pretend m

n−1 X

k m−1 = nm

k=0

is true for some n ≥ 0 Then n n−1 X X m−1 m k =m k m−1 + mnm−1 k=0

k=0 m

= n + mnm−1

The Fundamental Theorem of the Sum and Difference Calculus Pretend m

n−1 X

k m−1 = nm

k=0

is true for some n ≥ 0 Then n n−1 X X m−1 m k =m k m−1 + mnm−1 k=0

k=0 m

= n + mnm−1 = [n(n − 1) · · · (n − m + 1)] + [m(n(n − 1) · · · (n − m +

The Fundamental Theorem of the Sum and Difference Calculus Pretend m

n−1 X

k m−1 = nm

k=0

is true for some n ≥ 0 Then n n−1 X X m−1 m k =m k m−1 + mnm−1 k=0

k=0 m

= n + mnm−1 = [n(n − 1) · · · (n − m + 1)] + [m(n(n − 1) · · · (n − m + = n(n − 1) · · · (n − m + 2)[(n − m + 1) + m]

The Fundamental Theorem of the Sum and Difference Calculus Pretend m

n−1 X

k m−1 = nm

k=0

is true for some n ≥ 0 Then n n−1 X X m−1 m k =m k m−1 + mnm−1 k=0

k=0 m

= n + mnm−1 = [n(n − 1) · · · (n − m + 1)] + [m(n(n − 1) · · · (n − m + = n(n − 1) · · · (n − m + 2)[(n − m + 1) + m] = (n + 1)n(n − 1) · · · (n − m + 2)

The Fundamental Theorem of the Sum and Difference Calculus Pretend m

n−1 X

k m−1 = nm

k=0

is true for some n ≥ 0 Then n n−1 X X m−1 m k =m k m−1 + mnm−1 k=0

k=0 m

= n + mnm−1 = [n(n − 1) · · · (n − m + 1)] + [m(n(n − 1) · · · (n − m + = n(n − 1) · · · (n − m + 2)[(n − m + 1) + m] = (n + 1)n(n − 1) · · · (n − m + 2) = (n + 1)m

The Fundamental Theorem of the Sum and Difference Calculus

The fundamental theorem of the sum and difference calculus is m

n−1 X k=0

k m−1 = nm

The Fundamental Theorem of the Sum and Difference Calculus

The fundamental theorem of the sum and difference calculus is m

n−1 X

k m−1 = nm

k=0

Notice the analogy with the fundamental theorem of calculus Z m x m−1 dx = x m

Exponential Beat Powers The exponent 2n grows faster than the polynomial n2

Exponential Beat Powers The exponent 2n grows faster than the polynomial n2 Prove n2 ≤ 2n for all n > 3

Exponential Beat Powers The exponent 2n grows faster than the polynomial n2 Prove n2 ≤ 2n for all n > 3 For n = 4 we have 42 = 1624

Exponential Beat Powers The exponent 2n grows faster than the polynomial n2 Prove n2 ≤ 2n for all n > 3 For n = 4 we have 42 = 1624 Pretend n2 ≤ 2n for some n ≥ 4

Exponential Beat Powers The exponent 2n grows faster than the polynomial n2 Prove n2 ≤ 2n for all n > 3 For n = 4 we have 42 = 1624 Pretend n2 ≤ 2n for some n ≥ 4 Notice that (n + 1)2 ≤ 2n2 ,

when n > 3

since 0 ≤ 2n2 − (n + 1)2 = n2 − 2n − 1 = (n − 1)2 − 2

Exponential Beat Powers The exponent 2n grows faster than the polynomial n2 Prove n2 ≤ 2n for all n > 3 For n = 4 we have 42 = 1624 Pretend n2 ≤ 2n for some n ≥ 4 Notice that (n + 1)2 ≤ 2n2 ,

when n > 3

since 0 ≤ 2n2 − (n + 1)2 = n2 − 2n − 1 = (n − 1)2 − 2 Therefore

Exponential Beat Powers The exponent 2n grows faster than the polynomial n2 Prove n2 ≤ 2n for all n > 3 For n = 4 we have 42 = 1624 Pretend n2 ≤ 2n for some n ≥ 4 Notice that (n + 1)2 ≤ 2n2 ,

when n > 3

since 0 ≤ 2n2 − (n + 1)2 = n2 − 2n − 1 = (n − 1)2 − 2 Therefore

Exponential Beat Powers The exponent 2n grows faster than the polynomial n2 Prove n2 ≤ 2n for all n > 3 For n = 4 we have 42 = 1624 Pretend n2 ≤ 2n for some n ≥ 4 Notice that (n + 1)2 ≤ 2n2 ,

when n > 3

since 0 ≤ 2n2 − (n + 1)2 = n2 − 2n − 1 = (n − 1)2 − 2 Therefore (n + 1)2

Exponential Beat Powers The exponent 2n grows faster than the polynomial n2 Prove n2 ≤ 2n for all n > 3 For n = 4 we have 42 = 1624 Pretend n2 ≤ 2n for some n ≥ 4 Notice that (n + 1)2 ≤ 2n2 ,

when n > 3

since 0 ≤ 2n2 − (n + 1)2 = n2 − 2n − 1 = (n − 1)2 − 2 Therefore (n + 1)2 = 2n2

Exponential Beat Powers The exponent 2n grows faster than the polynomial n2 Prove n2 ≤ 2n for all n > 3 For n = 4 we have 42 = 1624 Pretend n2 ≤ 2n for some n ≥ 4 Notice that (n + 1)2 ≤ 2n2 ,

when n > 3

since 0 ≤ 2n2 − (n + 1)2 = n2 − 2n − 1 = (n − 1)2 − 2 Therefore (n + 1)2 = 2n2 ≤ 2 · 2n

Exponential Beat Powers The exponent 2n grows faster than the polynomial n2 Prove n2 ≤ 2n for all n > 3 For n = 4 we have 42 = 1624 Pretend n2 ≤ 2n for some n ≥ 4 Notice that (n + 1)2 ≤ 2n2 ,

when n > 3

since 0 ≤ 2n2 − (n + 1)2 = n2 − 2n − 1 = (n − 1)2 − 2 Therefore (n + 1)2 = 2n2 ≤ 2 · 2n = 2n+1

Induction Over Products Define the product notation n−1 Y k=0

Q

ak by

ak = a0 a1 · · · an−1

Induction Over Products Define the product notation n−1 Y

Q

ak by

ak = a0 a1 · · · an−1

k=0

Prove by induction that  n  Y 1 n+1 1− 2 = k 2n

k=2

for n ≥ 2

Induction Over Products Define the product notation n−1 Y

Q

ak by

ak = a0 a1 · · · an−1

k=0

Prove by induction that  n  Y 1 n+1 1− 2 = k 2n

for n ≥ 2

k=2

For a basis, let n = 2, and find  2  Y 1 2+1 1 1− 2 =1− 2 = k 2 2·2

k=2

Induction Over Products Pretend that  n  Y 1 n+1 1− 2 = k 2n

k=2

for some n ≥ 2

for n ≥ 2

Induction Over Products Pretend that  n  Y 1 n+1 1− 2 = k 2n

k=2

for some n ≥ 2 Then notice that

for n ≥ 2

Induction Over Products Pretend that  n  Y 1 n+1 1− 2 = k 2n

k=2

for some n ≥ 2 Then notice that

for n ≥ 2

Induction Over Products Pretend that  n  Y 1 n+1 1− 2 = k 2n

k=2

for some n ≥ 2 Then notice that  n+1 Y 1 1− 2 k k=2

for n ≥ 2

Induction Over Products Pretend that  n  Y 1 n+1 1− 2 = k 2n

for n ≥ 2

k=2

for some n ≥ 2 Then notice that  "Y #   n  n+1 Y 1 1 1 1− 2 1− 2 = 1− k k (n + 1)2 k=2

k=2

Induction Over Products Pretend that  n  Y 1 n+1 1− 2 = k 2n

for n ≥ 2

k=2

for some n ≥ 2 Then notice that  "Y #   n  n+1 Y 1 1 1 1− 2 1− 2 = 1− k k (n + 1)2 k=2 k=2    n+1 1 = 1− 2n (n + 1)2

Induction Over Products Pretend that  n  Y 1 n+1 1− 2 = k 2n

for n ≥ 2

k=2

for some n ≥ 2 Then notice that  "Y #   n  n+1 Y 1 1 1 1− 2 1− 2 = 1− k k (n + 1)2 k=2 k=2    n+1 1 = 1− 2n (n + 1)2   1 1 = (n + 1)2 − 2n (n + 1)

Induction Over Products Pretend that  n  Y 1 n+1 1− 2 = k 2n

for n ≥ 2

k=2

for some n ≥ 2 Then notice that  "Y #   n  n+1 Y 1 1 1 1− 2 1− 2 = 1− k k (n + 1)2 k=2 k=2    n+1 1 = 1− 2n (n + 1)2   1 1 = (n + 1)2 − 2n (n + 1)  2  1 n + 2n = 2n (n + 1)

Induction Over Products Pretend that  n  Y 1 n+1 1− 2 = k 2n

for n ≥ 2

k=2

for some n ≥ 2 Then notice that  "Y #   n  n+1 Y 1 1 1 1− 2 1− 2 = 1− k k (n + 1)2 k=2 k=2    n+1 1 = 1− 2n (n + 1)2   1 1 = (n + 1)2 − 2n (n + 1)  2  1 n + 2n = 2n (n + 1) n+2 = 2(n + 1)