Proof by induction has three parts:

a) basis step is proved

b) inductive hypothesis is assumed

c) proof of induction step

Show S _i=1ⁿ i = n(n+1) /2 by induction.

NOTE: Please be careful in setting up inductive proofs! Show all aspects clearly.

Basis: n=1. We have S _i=1¹ i = 1 = 1(1+1)/2.

Inductive hypo. S _i=1^k i = k(k+1)/2 i.e. True up though some k.

Show true for k+1.

SHOW WHAT? S _i=1^k+1 i = (k+1)[(k+1)+1]/2. When doing a proof, make sure the target is well in mind.

S _i=1^k+1 i = S _i=1^k i + (k+1)

= (k²+k)/2 + (2k+2)/2

= (k²+3k+2)/2

= (k+1)(k+2)/2

= (k+1)[(k+1) + 1] / 2 QED

Consider the Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, ...

F0=0; F1=1; F2=1; F3=2; F4=3

In general, F_n = F_n-1 + F_n-2.

Use induction to show that F_n < (5/3)ⁿ.

Basis: n=0 F0 = 0 < (5/3)⁰ = 1

n=1 F1 = 1 < (5/3)¹ QED

Inductive hypo: F_i < (5/3)ⁱ for i = 1, 2, ..., k

SHOW WHAAAT EXACTLY?

F_k+1 = F_k + F_k-1

Prove: there are infinitely many prime numbers.

Proof:

Assume not. (That is, assume there are finitely many primes.) Let P = {p1, p2, ..., p_n} lists all the primes where p_n is assumed to be the largest.

Consider N = p₁p₂...p_n + 1. N is not divisible by any number other than itself and 1, and is therefore prime. But N > p_n. Contradiction, since p_n assumed largest.

Therefore, the initial assumption is wrong. and there are finitely many primes.

Show that F_k £ k² is false.

Looks okay with F₈ = 34 < 8² = 64

But F₁₃ = 233 > 13² = 169. A counter example.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233...

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13

(i) Without repetition

Given: n objects. Any linear listing of these objects where order is important is called an arrangement of these objects. If the objects are distinct and repetition is not allowed such an arrangement is called a permutation.

The number of ways to form a permutation of size r from n distinct objects is given by: (from the rule of product)

This is denoted P(n,r)

The number of ways to arrange the letters in COMPUTER is 8!. (All letters are distinct.)

What if the letters are not distinct? For example, how many arrangements of the letters of the word BALL are there?

Note that the answer 4!=24 assumes that the "L's" are distinct. We have to divide that by 2!, the number of ways to arrange the two "L's" to get the final answer: 4!/2!=12.

n^r = # ways to have size r arrangement of n distinct objects with repetition

Standard deck of 52 cards, want to choose hands of size 3 from these cards. If the order of our choice is important, there are P(52,3) = 52!/(52 - 3)! = 22,100 ways.

If order is not important, the 3! permutations within a given hand are considered the same hand. This is called a selection, or combination, and the number of combinations of size r from n distinct objects is given by:

C(n,r) = (ⁿ_r) = P(n,r) / r! = n! / r!(n-r)! 0£ r£ n

Example the number of ways to choose 6 numbers from 50 (lottery) is (⁵⁰₆) = 15,890,700.

Number of ways to select, with repetition, a set of size r from n distinct objects is:

(n+r-1)!/r!(n-1)! = (^n+r-1_r)

Example Donut shop has 10 different kinds of donuts. Assuming there are at least 12 of each kind, how many ways are there of selecting a dozen donuts?

_________________

Example How many integer solutions to the equation x1 + x2 + x3 + x4 = 7 are there?

One solution is x1=3, x2=3, x3=0, x4=1. Different from x1=1, x2=0, x3=3, x4=3.

How represent these as lists of variables? Note order not important.

Therefore, answer is the number of ways of choosing a set of size 7 from {x1, x2, x3, x4} with repetition = ____________

Same as distributing 7 identical objects among 4 distinct containers.

Note that in Discrete 1, it is stated that the following are equivalent:

a) # of integer solutions to x₁+x₂+ ... x_n = r, x_i³ 0, 1£ i£ n

b) number of selections, with repetition, of size r from n objects

c) number of ways r identical objects can be distributed among n distinct containers

These are all equal to C(n+r-1, r) = (^n+r-1_r).

If x and y are variables and n is a positive integer:

(x+y)ⁿ = (ⁿ₀)x⁰yⁿ + (ⁿ₁)x¹y^n-1 + ... + (ⁿ_n)xⁿy⁰ = S _k=0ⁿ (ⁿ_k)x^ky^n-k.

Proof: Consider the coefficient of the general term x^ky^n-k. Since (x+y)ⁿ = (x+y)(x+y) ... (x+y), the coefficient of x^ky^n-k is the number of ways to select k x's from n available factors = (ⁿ_k).

Consider the following examples:

a) coeff of x⁵y² in expansion of (x+y)⁷ is:

b) coeff of a⁵b² in expansion of (2a-3b)⁷ is: _.

c) C(n,0) + C(n,1) + ... + C(n,n) = ?

d) C(n,0) – C(n,1) + ... (-1)ⁿC(n,n) = ?

e.g. A-B = {x | xÎ A and xÏ B}.

1. Definitions

Let A and B be sets. Consider the following definitions:

cross product of A and B: AxB = {(a,b) | aÎ A, bÎ B} set of ordered pairs, etc.

relation R from A to B: any subset of AxB

binary relation on A any subset of AxA (i.e. defined from A to A)

1. Let A = {1,2,3,4}, B={2,3,4). Then R_{1 =} {(2,3), (4,4)} is a relation on AxB.
2. define £ on Z. Let R₂ = {(a,b) | a,bÎ Z and a£ b}. Note binary relation.
3. define < on Z. Let R₃ = {(a,b) | a,bÎ Z and a<b}
4. for nÎ N = {0,1,2,...} define modulo n relation, º _n, on N by:
   " x,yÎ N: [x º _n y Û $ l Î Z st x-y = l n]. Another way to write: R₄ = {(x,y) | x,yÎ N and xº _n y}

Relations can be indicated by aRb, or by saying that (a,b)Î R.

Note that relations over finite sets can be modeled as a 0,1 matrix, where a 1 in matrix position M[i,j] indicates that ordered pair (i,j) is in the relation.

Let |A|=n. How many binary relations are there on A?

2. Binary relation R on a set A is reflexive if aRa, for all aÎ A. (a,a) Î R.

Let A = {1,2,3,4}.

Consider R1 = {(1,1),(2,2),(3,3), (1,3),(4,4), (4,2)} Reflexive?

Consider R2 = {(1,1),(2,2),(1,2)} Reflexive?

Note that (2), (4) are reflexive, (3) is not.

How many reflexive binary relations are there on A?

There are 2^(n²-n) reflexive binary relations on A. (Because the diagonal elements must be there... no choice.)

3. Binary relation R on set A is symmetric if " a,bÎ A, aRb Þ bRa.

(2), (3) are not symmetric. (4) is.

How many symmetric binary relations are there?

***

Divide AxA into two subsets A1 = {(a_i,a_i) | 1£ i£ n} and A2 = {(a_i, a_j) | 1£ i,j£ n, i¹ j}. A₁ refers to the elements on the diagonal of an nxn matrix; A₂ refers to all those elements not on the diagonal. Note |A1| = n, and |A2| = n²-n. [Note that n²-n is even!!] Consider subsets in A2 of the form S_ij = {(a_i, a_j), (a_j, a_i)} where 1£ i<j£ n. (This constraint forces the first choice to be from the lower part of the n x n matrix.) Note that there are (n²-n)/2 subsets of this form in A2.

To make a symmetric relation, we can include subsets of A1, and for each of those, subsets of the form S_ij from A2. This leads to symmetric relations on A.

How many binary relations are both symmetric and reflexive?

4. Binary Relations are transitive if " x,y,zÎ A, (x,y),(y,z)Î R Þ (x,z)Î R.

(2), (3), (4) are transitive

There is no easy way to calculate the number of transitive relations.

5. Equivalence Relations are reflexive, symmetric, and transitive.

Only (4) is an equivalence relation. Prove this.

1. Definitions

Given non-empty sets A, B, a function f from A to B, denoted f:A® B, is a relation from A to B where every element of A appears exactly once as the first component of an ordered pair. If relation f is a function and (a,b),(a,c)Î f, then b=c.

If (a,b)Î f, then we write f(a)=b.

Know meaning of domain, co-domain (B), range (f(A)).

If |A|=m and |B|=n, how many possible functions are there between A and B?

2. 1-1 functions (t255)

A function f:A® B is one-to-one (injective), if each element of B appears at most once as an image of an element of A. This means that " a1,a2Î A, f(a1)=f(a2)Þ a1=a2. If A and B are finite, then |A| £ |B|.

Let A = {1,2,3}, B={1,2,3,4,5}.

Then f={(1,1), (2,3), (3,4)} is 1-1 but

g={(1,1), (2,3), (3,3)} is not ("3" appears twice as an image of A)

f: R® R, where f(x) = 3x+7 " xÎ R.

Then " x1,x2Î R, we have:

f(x1)=f(x2) Þ 3x1 + 7 = 3x2 + 7

Þ 3x1 = 3x2

Þ x1 = x2.

Note that f: R® R, where f(x) = x² is not 1-1. (f(1) = f(-1), but 1¹ -1)

How many 1-1 functions are there A® B?

3. ONTO functions (t260)

A function f: A® B is onto, or surjective, if f(A) = B. That is, " bÎ B, $ aÎ A such that f(a)=b.

Note that f(x) = x³ is onto. f: R® R. " rÎ R, (r)^1/3 Î R and ((r)^1/3)³ = r.

But f(x) = x² is not onto.