Maths1 - Proofs

2.3 ) SQRT(2) is irrational [statement + proof]

(proof by contradiction)

1) suppose the statement is false (sqrt(2) is rational)

2) This means it can be written as m/n

3) Take m,n tobe in lowest terms (hcf(m,n)=1

4)Square the equation (m²=2n²)

5)Odd/even (if m was odd, m² is odd but m² is clearly even then m=2k)

6)n²=2k² when we make them equal so n is also even

7) if both m and n are even they are not in their lowest terms.

Contradiction → sqrt(2) is not rational

6.1 De Moivre’s Theorem [statement + proof]

Let z1,z2 be complex numbers with polar forms

Z1 = r1 (cosx1 + isinx1), z1= r2(cosx2+isinx2)

Then the product : z1z2=r1r2(cos(x1+x2)+isin(x1+x2))

In other words, z1z2 has modulus r1r2 and argument x1+x2

PROOF: We have

Z1z2 = r1r2 (cosx1+isinx1)(cosx2+isinx2)

Expand the bracket and get to the theorem.

7.1 The fundamental theorem of algebra [statement]

Every polynomial equation of degree at least 1 has a root in C.

9.1 & 9.2 Euler’s formula [statement]

9.1 For a convex polyhedron with V vertices, E edges and F faces, we have

V-E+F =2

9.2 If a connected plane graph has vertices, e edges and f faces, then

V - e +f = 1

12.1 There are infinitely many prime numbers [s+p]

Prrof by contradiction

1) assume the statement is false (finitely many prime numbers, p1,p2…pn)

2) Define a positive integer (N=p1p2…p3+1)

3)(not from the book) Then N is also a prime since when divided by any of the divisors there will be 1 left. But it is not on the prime list.

This is a contradiction.

What is the Fundamental Theorem of Arithmetic?

The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be expressed uniquely as a product of prime numbers, up to the order of the factors.

What is the existence proof of the Fundamental Theorem of Arithmetic?

Existence is proven by showing that every integer greater than 1 can indeed be factored into prime numbers. This is done using the well-ordering principle, which states that every non-empty set of positive integers has a least element.

Base: smallest integer greater than 1 = 2 . 2 is prime so its prime factorisation is 2

Inductive: n+1 : if n+1 is prime then its prime factorisation is n+1. If not prime, can be expressed as product of a and b where 1<=a,b<=n . Both a and b can be factored into primes therefore n+1 = ab can also be factored into primes

What is the uniqueness proof of the Fundamental Theorem of Arithmetic?

Uniqueness is proven by contradiction. If an integer can be factored into two distinct sets of primes, it leads to a violation of the definition of prime numbers and the properties of divisibility, confirming that the factorization must be unique.

Assumption: assume n can be factored into primes in two different ways p1p2…pk and q1q2…ql where p and k are primesk and l positive integers

Euclid's lemma: if a prime, p, divides the product of two integers a and b then p must divide at least one of a or b.

Applying Euclid's lemma: if p1 divides n=q1q2…ql then by the lemma, p1 must divide at least one of qs. (Lets say q1) Since p1 and q1 are both primes, p1=q1. By repeating this k=l meaning two factorisation is identical.

Differentiation formulae: Power [s+p]

If n is a positive integer, d/dx (xⁿ )= nx^n-1

Proof 1:

• The formula xⁿ - aⁿ = (x-a) (x^n-1 + …xa^n-2 + a^n-1 ). Multiply the RHS to verify

• If f(x) = xⁿ , use tangent line equation f’(a)= lim x→a (xⁿ - aⁿ )/x-a .

• Use first formula to expand limit and get na^n-1

Proof 2;

• F'(x) = lim h → 0 [f(x+h)-f(x)]/h (first principles)

• = Lim h→ 0 [(x+h)ⁿ - xⁿ ]/h

• Expand with binomial theorem

Differentiation formulae: constant multiple [s+p]

If c is a constant and f is a differentiable function, d/dx [cf(x)] = c d/dx f(x)

Proof

• Let g(x) = cf(x) and write g’(x) with first principle

Differentiation formulae: Chain Rule [s]

If g is differentiable at x and f is differentiable at g(x), then the composite function F = fog defined by F(x) = f(g(x))is differentiable at x and F’ is given by the product

F'(x) = f’(g(x))*g’(x)

• Leibniz notation , if y=f(u) and u = g(x) are both differentiable functions, then

  Dy/dx = dy/du * du/dx

Differentiation formulae: The Product Rule, The Quotient rule [s+p}

• Define F(x)

• Use first principles to differentiate F (x)

• Subtract and add f(x+h)g(x) (product rule) f(x)g(x) (quotient rule)

• Apply the limit (substitute h with zero)

14.1 Fermat’s Little Theorem [s}

16.2 & 16.3 Binomial and multinomial theorems [s+p]

Binomial theorem proof:

1)Consider (a+b)^n = (a+b)(a+b)…(a+b)

2) when we multiply this out to get a term a^(n-r)b^r, we choose the b from r of the brackets and the a from the other n-r brackets.

3) so the number of way of getting a^(n-r)b^r is the number of ways of choosing r brackets from n

Multinomial theorem proof:

1) consider (x1+…+xk)^n =(x1+…+xk)(x1+…+xk)…(x1+…xk)

2) expanding this, we get a term x1^r1….xk^rk by choosing x1 from r1 of the brackets, x2 from r2 brackets and so on.

£) the number of ways of doing this is n choose r1, …. rk

17.1 The inclusion-exclusion principle [s+p]

Let n be a positive integer, and let A1,…,An be finite sets. Then

|A1U…UAn| = c1-c2+c3-…+(-1)^n cn,

Where for 1<=i<=n, the number ci is the sum of the sizes of the intersections of the sets taken i at a time.

Proof:

…

21.1 The real numbers are uncountable [s+p]

21.5 The powerset of a set has strictly larger cardinality [s+p]

26.1 The subgroup test [s+p]

26.1 Lagrange’s Theorem [s+p]