Please enable JavaScript.
Coggle requires JavaScript to display documents.
Topic 3: Recursion and Induction - Coggle Diagram
Topic 3: Recursion and Induction
Induction
Reason to proof by induction
Proposition 2
The sum of the first n positive integers is n(n+1)/2
Proposition 1
The sum of the first n positive odd integers is n^2
Proof by induction
A technique for proving certain types of mathematical statements is true for all positive integers, or for all positive integers from some point on.
Type of statement
Summation formulas
Prove that 1+2+2^2+...+2^n = 2^(n+1) - 1, for all integers n > 0
Divisibility results
Prove that n^3 - n is divisible by 3 for every positive integer n
Inequalities
Prove that 2^n < n! for every positive integer n with n >4
Result about sets
Prove that if S is a set with n element, where n is a nonnegative integer
S has 2^n subsets
Result about algorithms
Prove that procedure FAC(n) returns n! for all nonnegative integers
3 Steps to prove using Mathematical Induction
Inductive Hypothesis
Assume P(k) is true
Inductive Step
Show that P(k+1) is true on the basis of the inductive hypothesis
Inductive Base
Show that P(1) [or P(0)] is true
Principle of Mathematical Induction
Prove P(n) is true for all positive integers
P(1) is true
For all k ≥ 1, P(k + 1) is true whenever p(k) is true: p(k) -> P(k+1)
Recursion
defined recursively
Some finite set of values, usually the first one or first few, are specified
The remaining values of the sequence are defined in terms of the PREVIOUS VALUES of the sequence
Definition is called recursive or inductive definition
Formula is called recursive formula or recursive relation
FORMULAE or recursive relation
sometime is difficult to define an object explicitly, but it may be easy to define this object in term of itself.
Recursive Definition
ƒ(0) = 1
ƒ(n+1) = 2ƒ(n) for n = 0, 1, 2, 3, 4, …..
Fibonacci Sequence
Make Spiral
Golden Ratio
Interesting Pattern
Sequence
Arithmetic Sequence
a is the first term
d is the common difference
difference betwwen one tern and the next
equation of nth term
equation of the sum of first n term
Geometric Sequence
r is the common ratio
equation of nth term
a is the first term
equation of the sum of first n term
