[go: up one dir, main page]
Scribd
Upload
43 views12 pages

Proofs by Counterexample & Contradiction: There Are Several Ways To Prove A Theorem

The document discusses different methods of mathematical proof including proofs by counterexample, contradiction, and induction. It provides examples of proofs by induction, showing the base case, inductive hypothesis, and induction step. It also discusses big O notation and limits for analyzing the asymptotic behavior of functions.

Uploaded by

Ayoade Akintayo Michael
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
43 views12 pages

Proofs by Counterexample & Contradiction: There Are Several Ways To Prove A Theorem

The document discusses different methods of mathematical proof including proofs by counterexample, contradiction, and induction. It provides examples of proofs by induction, showing the base case, inductive hypothesis, and induction step. It also discusses big O notation and limits for analyzing the asymptotic behavior of functions.

Uploaded by

Ayoade Akintayo Michael
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 12

Proofs by Counterexample &

Contradiction
There are several ways to prove a theorem:
 Counterexample:
 By providing an example of in which the theorem
does not hold, you prove the theory to be false.
 For example: All multiples of 5 are even.
However 3x5 is 15, which is odd. The theorem is
false.

 Contradiction:
 Assume the theorem to be true. If the
assumption implies that some known property is
false, then the theorem CANNOT be true.

1
Proof by Induction
 Proof by induction has three standard parts:
 The first step is proving a base case, that is,
establishing that a theorem is true for some small
value(s), this step is almost always trivial.
 Next, an inductive hypothesis is assumed.
Generally this means that the theorem is assumed
to be true for all cases up to some limit n.

 Using this assumption, the theorem is then shown


to be true for the next value, which is typically n+1
(induction step). This proves the theorem (as
long as n is finite).
2
Example: Proof By Induction
 Claim: S(n) is true for all n >= k
 Basis:
 Show formula is true when n = k
 Inductive hypothesis:
 Assume formula is true for an arbitrary n
 Induction Step:
 Show that formula is then true for n+1

3
Induction Example: Gaussian Closed
Form
 Prove 1 + 2 + 3 + … + n = n(n+1) / 2
 Basis:
 If n = 0, then 0 = 0(0+1) / 2
 Inductive hypothesis:
 Assume 1 + 2 + 3 + … + n = n(n+1) / 2
 Step (show true for n+1):
1 + 2 + … + n + n+1 = (1 + 2 + …+ n) + (n+1)
= n(n+1)/2 + n+1 = [n(n+1) + 2(n+1)]/2
= (n+1)(n+2)/2 = (n+1)(n+1 + 1) / 2

4
Induction Example: Geometric
Closed Form
 Prove
 a0 + a1 + … + an = (an+1 - 1)/(a - 1) for all a  1
 Basis: show that a0 = (a0+1 - 1)/(a - 1)
a0 = 1 = (a1 - 1)/(a - 1) = 1
 Inductive hypothesis:
 Assume a0 + a1 + … + an = (an+1 - 1)/(a - 1)
 Step (show true for n+1):
a0 + a1 + … + an+1 = a0 + a1 + … + an + an+1
= (an+1 - 1)/(a - 1) + an+1 = (an+1+1 - 1)/(a - 1)

5
Limits
 lim [f(n) / g(n)] = 0  f(n)  (g(n))
n

 lim [f(n) / g(n)] <   f(n)  (g(n))


n

 0 < lim [f(n) / g(n)] <   f(n)  (g(n))


n

 0 < lim [f(n) / g(n)]  f(n) (g(n))


n

 lim [f(n) / g(n)] =   f(n)  (g(n))


n

6
Useful Facts
 For a  0, b > 0, lim n ( lga n / nb ) = 0,
so lga n = o(nb), and nb = (lga n )

 lg(n!) = (n lg n)

7
Examples
A B
 log3(n2) log2(n3)

 nlg4 3lg n

 lg2n n1/2

9
Examples
A B
 log3(n2) log2(n3) A  (B)
logba = logca / logcb; A = 2lgn / lg3, B = 3lgn, A/B =2/(3lg3)

 nlg4 3lg n

 lg2n n1/2

10
Examples
A B
 log3(n2) log2(n3) A  (B)
logba = logca / logcb; A = 2lgn / lg3, B = 3lgn, A/B =2/(3lg3)

 nlg4 3lg n A  (B)


alog b = blog a; B =3lg n=nlg 3; A/B =nlg(4/3)   as n

 lg2n n1/2

11
Examples
A B
 log3(n2) log2(n3) A  (B)
logba = logca / logcb; A = 2lgn / lg3, B = 3lgn, A/B =2/(3lg3)

 nlg4 3lg n A  (B)


alog b = blog a; B =3lg n=nlg 3; A/B =nlg(4/3)   as n

 lg2n n1/2 A  (B)


lim ( lga n / nb ) = 0 (here a = 2 and b = 1/2)  A  (B)
n

12
End of Chapter 3

14

You might also like