[PDF] Mathematical induction & Recursion

Math 312, Intro to Real Analysis: Homework  Solutions

10 8 Assume that (sn) is a nondecreasing sequence of real numbers Let σn be the average of the first n numbers in our given sequence: σn = s1 +··· +sn n We claim that the sequence (σn) is again nondecreasing

Series - UC Davis Mathematics

4 1 Convergence of series 61 Telescoping series of the form X1 n=1 (a n a n+1) are another class of series whose partial sums S n= a 1 a n+1 can be computed explicitly and then used to study their convergence

01 Degrees

10 Sn hasacontinuousfieldofnon-zerotangentvectorsifandonlyifnisodd Proof Suppose x7v(x) is a tangent vector field on Sn, assigning to a vector x2 Sn the vector

Chapter 3

22 3 Continuous Functions If c ∈ A is an accumulation point of A, then continuity of f at c is equivalent to the condition that lim xc f(x) = f(c), meaning that the limit of f as x → c exists and is equal to the value of f at c

The Definition of a Manifold and First Examples

WOMP 2012 Manifolds Jenny Wilson The Definition of a Manifold and First Examples In brief, a (real) n-dimensional manifold is a topological space Mfor which every point x2Mhas a neighbourhood

Homework  { corrections

Math 320: Analysis I Spring 2015 By the Completeness Axiom, supfs n: n > Ngand supft n: n > Ngexist and are real numbers Since supfs n: n > Ngand supft n: n > Ngare the least upper bounds for fs n: n > Ngand ft n: n > Ng, respectively, the last inequality in (1) implies s n+ t n supfs n: n > Ng+ supft n: n > Ng: (3)

Trig Cheat Sheet - Pauls Online Math Notes

Definition of the Trig Functions Right triangle definition For this definition we assume that 0 2 p

Math 412 The Orbit Stabilizer Theorem

(c)Karen E Smith 2018 UM Math Dept licensed under a Creative Commons By-NC-SA 4 0 International License Math 412 The Orbit Stabilizer Theorem Fix an action of a group G on a set X For each point x of X, we have two important concepts: DEFINITION: The orbit of x 2X is the subset of X O(x) := fg xjg 2GgˆX:

Mathematical induction & Recursion

Recursive definition of * • Basis step: – empty string * • Recursive step: –I wf * and x then wx * M Hauskrecht Length of a String Example: Give a recursive definition of l(w), the length of the string w Solution: The length of a string can be recursively defined by: l(‘’) = 0; the length of the empty string

[PDF] math forte secondaire 5

[PDF] cours l'air qui nous entoure

[PDF] controle chimie 4ème l'air qui nous entoure

[PDF] quel est le pourcentage du rayonnement solaire qui traverse effectivement l'atmosphère terrestre

[PDF] l'air qui nous entoure 4ème

[PDF] comment appelle t on la couche dans laquelle nous vivons

[PDF] qu'est ce que l'atmosphère terrestre

[PDF] qu'est ce qui mesure la quantité de vapeur d'eau

[PDF] synthese d'un anesthesique la benzocaine correction

[PDF] synthèse de la benzocaine seconde

[PDF] synthèse du 4-nitrobenzoate d'éthyle

[PDF] synthèse de la benzocaine exercice seconde

[PDF] synthèse de la benzocaine sujet

[PDF] synthèse de la benzocaine terminale s

[PDF] la benzocaïne est utilisée en médecine comme anesthésique local d'usage externe

1

M. HauskrechtCS 441 Discrete mathematics for CS

CS 441 Discrete Mathematics for CS

Lecture 15

Milos Hauskrecht

milos@cs.pitt.edu

5329 Sennott Square

Mathematical induction

& Recursion

M. HauskrechtCS 441 Discrete mathematics for CS

Proofs

Basic proof methods:

• Direct, Indirect, Contradiction, By Cases, Equivalences

Proof of quantified statements:

•There exists x with some property P(x). - It is sufficient to find one element for which the property holds. •For all x some property P(x) holds. - Proofs of 'For all x some property P(x) holds' must cover all x and can be harder. •Mathematical inductionis a technique that can be applied to prove the universal statements for sets of positive integers or their associated sequences. 2

M. HauskrechtCS 441 Discrete mathematics for CS

Mathematical induction

• Used to prove statements of the form x P(x) where x Z Mathematical induction proofs consists of two steps:

1) Basis:The proposition P(1) is true.

2) Inductive Step:The implication

P(n) P(n+1), is true for all positive n.

• Therefore we conclude x P(x). •Based on the well-ordering property: Every nonempty set of nonnegative integers has a least element.

M. HauskrechtCS 441 Discrete mathematics for CS

Mathematical induction

Example:Prove the sum of first n odd integers is n 2 i.e. 1 + 3 + 5 + 7 + ... + (2n - 1) = n 2 for all positive integers.

Proof:

• What is P(n)? P(n): 1 + 3 + 5 + 7 + ... + (2n - 1) = n 2

Basis StepShow P(1) is true

• Trivial: 1 = 1 2 Inductive StepShow if P(n) is true then P(n+1) is true for all n. • Suppose P(n) is true, that is 1 + 3 + 5 + 7 + ... + (2n - 1) = n 2 • Show P(n+1): 1 + 3 + 5 + 7 + ... + (2n - 1) + (2n + 1) =(n+1) 2 follows: • 1 + 3 + 5 + 7 + ... + (2n - 1) + (2n + 1) = n 2 + (2n+1) = (n+1) 2 3

M. HauskrechtCS 441 Discrete mathematics for CS

Correctness of the mathematical induction

Suppose P(1) is trueand P(n) P(n+1) is truefor all positive integers n. Want to show x P(x). Assume there is at least one n such that P(n) is false. Let S be the set of nonnegative integers where P(n) is false. Thus S . Well-Ordering Property:Every nonempty set of nonnegative integers has a least element. By the Well-Ordering Property, S has a least member, say k. k >

1, since P(1) is true. This implies k - 1 > 0 and P(k-1) is true

(since k is the smallest integer where P(k) is false).

Now:P(k-1) P(k) is true

thus, P(k) must be true (a contradiction). •Therefore x P(x).

M. HauskrechtCS 441 Discrete mathematics for CS

Mathematical induction

Example:Prove n < 2

n for all positive integers n. • P(n): n < 2 n

Basis Step:1 < 2

1 (obvious) Inductive Step:If P(n) is true then P(n+1) is true for each n. • Suppose P(n): n < 2 n is true • Show P(n+1): n+1 < 2 n+1 is true. n + 1 < 2 n + 1 < 2 n + 2 n = 2 n ( 1 + 1 ) = 2 n (2) = 2 n+1 4

M. HauskrechtCS 441 Discrete mathematics for CS

Mathematical induction

Example: Prove n

3 - n is divisible by 3 for all positive integers. • P(n): n 3 - n is divisible by 3

Basis Step:P(1): 1

3 - 1 = 0 is divisible by 3 (obvious) Inductive Step:If P(n) is true then P(n+1) is true for each positive integer. • Suppose P(n): n 3 - n is divisible by 3 is true. • Show P(n+1): (n+1) 3 - (n+1) is divisible by 3. (n+1) 3 - (n+1) = n 3 + 3n 2 + 3n + 1 - n - 1 = (n 3 - n) + 3n 2 + 3n = (n 3 - n) + 3(n 2 + n) divisible by 3 divisible by 3

M. HauskrechtCS 441 Discrete mathematics for CS

Strong induction

•The regular induction: - uses the basic step P(1)and - inductive step P(n-1) P(n) •Strong induction uses: - Uses the basis step P(1)and - inductive step P(1) and P(2) ... P(n-1) P(n) Example:Show that a positive integer greater than 1 can be written as a product of primes. 5

M. HauskrechtCS 441 Discrete mathematics for CS

Strong induction

Example:Show that a positive integer greater than 1 can be written as a product of primes. Assume P(n): an integer n can be written as a product of primes.

Basis step:P(2) is true

Inductive step:Assume true for P(2),P(3), ... P(n)

Show that P(n+1) is true as well.

2 Cases:

• If n+1 is a prime then P(n+1) is trivially true • If n+1 is a composite then it can be written as a product of two integers (n+1) = a*b such that 1< a ,b < n+1 • From the assumption P(a) and P(b) holds. • Thus, n+1 can be written as a product of primes •End of proof

M. HauskrechtCS 441 Discrete mathematics for CS

Recursive Definitions

• Sometimes it is possible to define an object (function, sequence, algorithm, structure) in terms of itself. This process is called recursion.

Examples:

• Recursive definition of an arithmetic sequence: -a n = a+nd -a n =a n-1 +d , a 0 = a • Recursive definition of a geometric sequence: •x n = ar n •x n = rx n-1 , x 0 =a 6quotesdbs_dbs15.pdfusesText_21