Transcript fabonacci(n-1)+

Chap 3
– A theorem is a statement that can be shown
to be true
– A proof is a sequence of statements to show
that a theorem is true
– Axioms: statements which are assumptions,
hypotheses or previously proved theorem
– Pales of inference: draw conclusion from
other assertions
Chap 3 (cont.)
– Lemma: simple theorems used to prove other
theorems
– Corollary: established from a theorem
– Modus ponens
P
PQ
∴ Q
– Table 1: rules of inference
Chap 3 (cont.)
– An argument is valid if whenever all the
hypotheses are true, the conclusion is also true
– if all propositions used in a valid argument are true,
if leads to a correct conclusion
– “if | o | is divisible by 3, than | 0 |2 is divisible by 9.
| o | is divisible by 3. Consequently, | 0 |2 is
divisible by 9.” is a valid argument; however, the
conclusion is false
– Example 6 & 7
[(PQ)  Q]  P is not a tautology
– fallacy of affirming the conclusion 
[(PQ)   Q]   Q is not a tautology
– fallacy of denying the hypothesis
n is an even integer whenever n2 is an even
integer suppose n2 is even, then n2 is = 2k
For some integer k.
Let n=2l for some integer l . This show n is ever .
– fallacy if begging the question
Table 2 rule of inference for quantified statements
Example 13
direct proof: If n is odd, then n2 is odd
n=2k+1, n2 =(2k+1)2 = 4k2 +4h+1
= 2(2k2 +2h)+1
n2 is odd
indirect proof: If 3n+2 is odd, n is odd
assume n is ever, n=2k
3n+2 = 3(2h)+2 = 2(3h+1)
3n+2 is even
P Q   Q  P
trivial proof: P(n): “If a and b are positive , a  b
then an an  bn “,show P(o) is true
If a  b, then a0  b0
since 1 1, P(o) is true
- Q is true, then P  Q is true
 Proof by contradiction: √2 is irrational
Let P: √2 is irrational
Suppose that  P is true, √2 is rational
√2 = a / b, a and b have no common factors
2 = a2 /b2
a 2 is even , a is even , a=2c
2b2=4c2
b2=2c2
b2 is even , b is even
contradiction!
—  PF is true
 P is false , P is true
 Rewrite an indirect proof by a proof by contradiction
 q  p is true then p  q is true
 q is true and show p must also true
Suppose p and p are true(proof by contradiction) use
direct proof  q  p to show p is also
true,contradiction
Example 19 : If 3n+2 is odd, n is odd
assume 3n+2 is odd and n is even
for n is even,we show 3n+2 is even, contradiction!
Proof by cases : If n is an integer not divisible by 3,
then n2  1(mod 3)
p: n is not divisible by 3
q: n2  1(mod 3)
p is equivalent to p1V p2,p1:n  1,p2 :n  2
[(p1V p2 V. ...pn)  q]  [(p1  q)(p2  q) …  (pn 
q)]
(p1V p2)  q
p q
(p  q)  [(p  q) (q  p) ]
Example 21: n is odd  n2 is odd
we show pq and q p are true
[ p1  p2 … pn ]  [ (p1  p2) …  (pn-1 
pn) pn p1) ]
Constructive existence proof
find an element a such that p(a) is true for
proving x p(x)
Nonconstructive existence proof
proof by constructive
Prove xp(x) is false
find an element a such that p(a) is false
xp(x) is true,  xp(x) is true, xp(x) is false
counterexample
Example 25
Example 26 (the truth of a statement cannot be
established by one or more examples)
every even positive integer greater than 4 is
the sum of two primes
–Goldbach’s conjecture
–no counterexample has been found
Mathematical Induction
– The sum of the first n positive cold integers,n2?
– P(n) is true for every positive integer n:
Basic step: P(n) is true
Inductive step: P(n)  P(n-1) is true for every
positive integer n –[P(1)n(P(n) P(n+1)] 
n P(n)
– Example 2,3,5,6,7,8,11,12
Second Principle of
Mathematical Induction
– P(n) is true for every positive integer n:
Basic step: P(1) is true
Inductive step: P(1) P(2) … P(m) P(m+1)
is true
– Example 13
P(n): n can be written as product of primes, n2
Basic step: P(2)
Second Principle of
Mathematical Induction, cont.
Inductive step:
assume P(k) is true for all positive integers k,
kn
i ) n+1 is prime
ii) n+1 is composite
n+1= a*b, 2  ab n+1
by inductive hypothesis, both a and b can be
written as product of primes
difficult to prove using principle of math.
Induction!
Example 14
P(n): postage of n cents can be formed
using 4-cent and 5-cent stamps, n12
Basic step: P(n) is true
Inductive step: P(n) is true
i) one 4-cent stamp is used
replace it with a 5-cent stamp
ii) no 4-cent stamps were used
n 12, at least three 5-cent were
used replace three 5-cent with
for 4-cent
Basic step: P(12), P(13),P(14) and P(15) are true
Inductive step: n15, k cents can be formed,
12 k n to form n+1, use n-3
cents and 4-cent
Application of Mathematical
Induction
An=2n, n=0,1,2,…
a0 =1
an+1 =2an, n=0,1,2,…
– recessive / inductive definitions
Example 1
f(0)=3
f(n+1)=2f(n)+3
Example 2
F(n)=n!
F(0)=1
F(n+1)=(n+1)F(n)
– Some recessive definitions of functions are
based on the second principle of
mathematical induction
Example 5 The Fibonacci numbers
f0=0, f1=1
fn=fn-1+fn-2, n=2,3,4…
Example 6 ( use fibonacci numbers to prove )
show fn>n-2 , =(1+√5)/2, n3
P(n): fn > n-2
Basic step: P(3) is true: f3=2 > 
P(4) is true: f4=3 >(3+√5)/2
=2
Inductive step: assume P(k) is true, 3kn, n4
2 = +1, n-1= 2 × n-3
=  × n-3+ n-3
= n-2+ n-3
fn-1>n-3, fn > n-2
∴ fn+1= fn +fn-1 > n-2+ n-3 =n-1
P(n+1) is true
Recursive algorithms
Definition 1 An algorithm is recursive if it
solves a problem by reducing it to
an instance of the same problem
with smaller input
Example 1 compute an where a is non  ero
and n  0 procedure power
(a:nonzero, n:nonnegative )
if n=0 than power (a, n):=1
else power (a,n):= a×power(a,n-1)
Example 5 compute n!
procedure factorial ( n:positive )
if n=1 than
factorial(n) : = 1
else factorial (n) : = n × factorial(n-1)
– a corresponding iterative procedure
procedure iterative factorial ( n:positive )
x:=1
for i : =1 to n
x : =i × x x is n!
Example 7 found the nth Fabonacci number
procedure fibonacci (n:nonnegative)
if n=0 then fibonacci(0):=0
else if n=0 then fibonacci(1):=1
else fabonacci(n):=fabonacci(n-1)+
fabonacci(n-2)
f4
f3
f2 f1
f1 f0
f2
f1 f0
procedure iterative fibonacci (n: nonnegative)
if n=0 than y:= 0
else
begin
x:=0
y:=1
for i:=1 to n-1
begin
z : = x+y
x:=y
y:=z
end
end
y is the nth fibonacci number
• Require n-1 addition to find fn
• Require far less computation
• A recursive procedure is sometimes
preferable
– eases to be implemented
– Machine designed to handle recursion