How to Prove it

Lecture 24
In this lecture he talks about the number $e$ using the compound interest approach. $\left ( 1+\frac{1}{n} \right )^n$ .
The second approach he uses is factorial. He shows that it is equal to $\sum_{n=0}^{\infty}\frac{1}{n!}=1$
The next proof is proving that $e$ is irrational. The proof is by contradiction.

Lecture 23
In this lecture he takes up Perfect numbers and Mersenne Primes. The ancient greeks knew about the first four perfect numbers $6,28,496, 8128$ .
A number is perfect if sum of proper divisors add to the number itself.
A number is perfect $2^{p-1}(2^p-)$ . If a number $n$ is a mersenne prime. A Mersenne prime is $n=2^{p}-1$ . Note not all primes give a mersenne prime. At present we only know $49$ mersenne primes (Jan 10,2017) and so we only know $49$ perfect numbers.
The lemma he introduces without proof are $\sigma(ab)=\sigma(a)\sigma(b)$
And if the numbers are $\sigma(p^n)=1+p+p^2+\cdots+p^n=\frac{p^{n+1}-1}{p-1}$ . Thus the number $\sigma(2^{p-1}(2^p-1))=\sigma(2^{p-1}\sigma(2^p-1))$
Now $\sigma(2^{p-1}) = 1+2+2^2+\cdots+2^{p-1}=2^p-1$ and $\sigma(2^p-1) = 1+2^p-1=2^p$ . Hence $\sigma{2^{p-1}(2^p-1)} = (2^p-1)2^p = 2\cdot 2^{p-1}(2^p-1)$

Lecture 22
This is a fun lecture and it talks about. Triangle Number, Square Number and Fibonacci Numbers.
First the nth triangle number is given by $\frac{n(n+1)}{2}$
First few triangle numbers are $\{1,3,6,10,15,21,28,36,45,55,\cdots\}$
First few square numbers are $\{1,4,9,25,36,49,64,\cdots \}$
Easy visual proof is $\text{Square Number} = t_n+t_{n-1}$
We notice that $1,36$ are both triangle numbers and perfect numbers.
Notice that $36$ is the 8th Triangular number. There is a theorem that $t_{8t_{n}}$ is a perfect square where $t_{n}$ itself is a square number.
He also proves by induction that sum of first $n^3= {t_n}^2$ .
The last thing he does in the lecture is to prove that there are only 5 Fibonacci numbers that are also triangular numbers.
Are there infinite number of triangle numbers that are Square Numbers ?

Lecture 21
This is a second lecture on Number theory. In this lecture he discusses the famous problems.
First is prime number theorem. So the answer is $\pi(n) =\frac{n}{\ln(n)}$

The 2nd is twin prime conjecture. That one can alway find two prime numbers that are alway just two numbers apart. He gives an example of 1,000,000,0000,061 and 1,000,000,0000,063 as two big twin primes. Nobody knows if there are infinite of these twin primes.

The 3rd is Goldbach conjecture. Given an even integer it can alway be expressed as sum of two primes. He also recommends the book Uncle Pedro

The last is collatz conjecture and he warns not to use 27 also called as $3n+1$ conjecture. Erdos said about this problem that mathematics is not yet ready to solve her problem.

He also mentions the perfect numbers. The perfect number are of the form whose proper divisors sum to that number and three such numbers are
$6, 28, 496$ .

Lecture 20
This lecture is about number theory. He talks about Prime Numbers.
Mathematics is the queen of Sciences but number theory is queen of sciences. A positive integer is a prime if it has only two divisors 1 and itself. Its due to Eratosthenese. He later talks about the twin primes that is still unsolved.

Is there a pattern among primes.
Sieve of Eratosthenes and you have to do it for $n \le n$ . Cross out all the multiples till $\le \sqrt{n}$ . Everything that is remaining are the prime numbers. Note this works for any finite set of numbers.

He then talks about the twin prime conjecture and that it is still unsolved. An anecdote about Erdos that he was late for the class and ended up solving the two out of 3 unsolved problem that his professor had put on the board.

Lecture 19
This is a lecture on Visual Proof.
The first pythagorean proof he does is of carving out 4 right triangles of sides $a$ and $b$ .
He goes over President Garfield’s proof of Pythagoras theorem. What he did was to construct a Trapezoid of sides $a,b,a+b$ and the remaining side. We calculate the area in two different ways and after cancelling we get the Pythagorean theorem.
The next construction proof he does is of AM-GM inequality where in a square he carves out four rectangles of $a,b$ and then we eliminate $(a-b)^2$ and get the inequality.
He also does the proof of sum of first $n$ natural numbers by taking a grid of $n$ by $n+1$ and using the staircase to show that there are two series of such case in $n(n+1)$ . He also proves this using the area of triangle at the end of the lecture. So we construct a right triangle with one square at the top, then two square, then three squares and so on till n square of unit area each at the bottom. Finally we draw a straight line as a hypotenuse to complete the right angled triangle. But there are $n$ triangles each split into half. The area of those is $\frac{n}{2}$ and the area of right angled triangle is $\frac{1}{2}n^2$ adding $\frac{n}{2}$ we get the total as $\frac{n(n+1)}{2}$ .
One of my favorite proof is that of geometric series inside the square. We start with a square of size $1$ by $1$ and then cut into half then on-fourth and so on filling the square and the limit is the full square.

Lecture 18

Lecture 17
He starts off with the lecture $n^2-n+41$ which gives primes for first $40$ numbers.He then moves to provide the counterexamples for the basic mistakes many high school students do.
$(a+b)^2=a^2+b^2$ ,
$\frac{1}{x+y}=\frac{1}{x}+\frac{1}{y}$ ,
$\ln(a+b)=\ln(a)+\ln(b)$ ,
$\sin(2x)=2\sin(x)$
He also mentions product rule (doesn’t give any example) but to prove that $(fg)' \ne f'g'$
He mentions the anecdote in his class where his friend in graduate class instead of paying attention to professor would spend time finding counter examples in class.
Fermat primes. These numbers are of the form $2^{2^n}+1$ . Starting with $n = 0$ and $n = 4$ , we see that we get $3,5,17,257,65537$ are all primes. Then Euler proved that for $n= 5$ the number $4294967297$ is not a prime, it can be factorized as $4294967297= 641\times 67006417$ . Now there is an unproven conjecture that for all $n\ge 5$ none of the Fermat primes are primes.
Paradoxes:
This statement is false.
Galileo’s matching of one to one correspondence between Natural Numbers and Even Integers.
Zeno’s paradox.Not getting started if one understands the idea of infinite geometric series.
Next week I am going to give you a test announced. It can’t be on friday.
Bertrand’s Paradox: There is a barber who cuts the hair of those people who do not cut their own hair.

Lecture 16
In this lecture he does proof by enumeration. The truth of the statement is demonstrated by taking all the individual cases.
$n^2+n$ is always even.
We can obviously verify that for cases by plugging in numbers.
If $n$ is even we have $(2k)^2+2k=4k^2+2k+2=(2k^2+k)$ is even
If $n$ is odd we have $(2k+1)^2+(2k+1)=4k^2+4k+1+2k+1=4k^2+6k+2=2(2k^2+3k+1)$ is again even.

Divide $\frac{n^2}{4}$ leaves a remainder

Do examples, do a million examples

He proves the triangle inequality

Lecture 15

Lecture 14

Lecture 13
The highlight of this lecture is the proof of the Binet Formula using Strong Induction.
The Binet formula is $\frac{\phi^n-\alpha^n}{\sqrt{5}}$
$\phi = \frac{1+\sqrt{5}}{2}$ and $\alpha = \frac{1-\sqrt{5}}{2}$ .
Verify the base cases:
for $n = 1$ we have
$\frac{\phi-\alpha}{\sqrt{5}}= 1$
Similarly
for $n = 2$ we have
$\frac{\phi^2-\alpha^2}{\sqrt{5}}$
$\Rightarrow \frac{(\phi-1)-(\alpha-1)}{\sqrt{5}}$
$\Rightarrow \frac{\phi-\alpha}{\sqrt{5}}$
which we know from first statement is true
To prove the last step we realize that $F_{n+1}=F_n+F_{n-1}$
Thus we have
$\Rightarrow F_{n+1}= \frac{\phi^n-\alpha^n}{\sqrt{5}}+\frac{\phi^{n-1}-\alpha^{n-1}}{\sqrt{5}}$
$\Rightarrow F_{n+1}= \frac{\phi^n+\phi^{n-1}-\alpha^n-\alpha^{n-1}}{\sqrt{5}}$
$\Rightarrow F_{n+1}= \frac{\phi^{n-1}(\phi+1)-\alpha^{n-1}(\alpha+1)}{\sqrt{5}}$
$\Rightarrow F_{n+1}= \frac{\phi^{n-1}(\phi^2)-\alpha^{n-1}(\alpha^2)}{\sqrt{5}}$
$\Rightarrow F_{n+1}= \frac{\phi^{n+1}-\alpha^{n+1}}{\sqrt{5}}$
Hence Proved

Lecture 12
General formula for Fibonacci numbers. Its called Binet Formula.
Aside from showing it is true for base case. The Strong Induction assumes that the given statement is true for all numbers between the one covered by the base case and an arbitrary number $n$ .

Every number is a Prime or a Product of Primes.

Lecture 11
This is the first lecture on Mathematical Induction and he proves the usual theorem
He first quotes Polya
It is enough to know two things about the conjecture
1. It is true for $n=1$
2. Being true for $n$ , its also true for $n+1$

First proof $S=\frac{n(n+1)}{2}$
Second proof $1+3+5+\cdots+(2n-1)= n^2$
Third proof $1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}{6}$
Fourth proof $1^3+2^3+\cdots+n^3=\left ( \frac{n(n+1)}{2}\right )^2$
The last example is to demonstrate that base case need not be $1$ its about inequality
$2^n > n^2$ for $n > 4$
So here the base case is $n = 5$

Lecture 10
Infinite Sets
Galileo noticed this paradox. Square is a subset of the set.
One set can be a subset of another set.
Measuring the size of the set.
Two sets have the same cardinality if there is a bijection $f:A \rightarrow B$
Cardinality of Integers
Bijective mapping between Natural numbers and Integers
$f(n) = \frac{n}{2}$ if $n$ is even.
$f(n) = \frac{-(n-1)}{2}$ if $n$ is odd.

A set is countably infinite if it has the same cardinality as Natural number.
So a countable set is either finite or countably infinite.
Rational numbers are countably infinite.
Bijection between Natural number and Fractions
$\frac{1}{1} \frac{2}{1}\frac{3}{1}\frac{4}{1}\frac{5}{1}$
$\frac{1}{2} \frac{2}{2}\frac{3}{2}\frac{4}{2}\frac{5}{2}$
$\frac{1}{3} \frac{2}{3}\frac{3}{3}\frac{4}{3}\frac{5}{3}$
$\frac{1}{4} \frac{2}{4}\frac{3}{4}\frac{4}{4}\frac{5}{4}$
$\frac{1}{5} \frac{2}{5}\frac{3}{5}\frac{4}{5}\frac{5}{5}$

Mapping interval (0,1)
Is there anything in between cardinality of Natural Number and cardinality of real numbers.
One can show that there is a 1 to 1 mapping between $(0,1) \rightarrow \frac{2x-1}{x(x-1)}$
Its impossible to disprove Continnum Hypothesis from axioms of set theory by Godel.
Its impossible to prove Continnum Hypothesis from axioms of set theory by Paul Cohen.

Lecture 9
Elementary Set theory
Set of all playing cards
He proves De Morgan’s law in this lecture.

Lecture 8

Lecture 7
Proof by Contradiction
He starts with the $\sqrt{2}$ is a rational number.
Contrapositive is the idea $p \rightarrow q$ and $\lnot q \rightarrow \lnot p$
The first proof he does is prove that $n^2 \text{is even} \rightarrow n \text{is even}$
This is also called as Reductio ad absurdum (Reduction to the absurd).
Polya said the “Reduction ad absurdum shows the falsity of the assumption by deriving from it a manifest absurdity”.

Question: Suppose you have $367$ students in the class prove that at least two have the same birthday.
Assume that each has a different birthday ie all have different birthday. Which means we have $367$ different birthday because we cannot have that because a normal year has only 365 or 366 different days.

The next proof is $\sqrt{2}$
The next proof he alludes the

GH Hardy
If $a+b$ is odd then either $a$ is odd or $b$ is odd.
$a \text{is odd or} b \text{b is odd}$ .
So we use proof by contradiction

If $x$ is Irrational then it square is also irrational.
False. Well here we have a counter example of $\sqrt{2}$ whose square is a rational.

If $x^2$ is Irrational than its square root is also irrational.
True. The proof hinges on the idea of proof by contradiction. Let $x$ is rational then $x^2$ is also rational ie $x=\frac{p}{q}, q \ne 0$ then $x^2 = \frac{p^2}{q^2}$ is also rational.

Lecture 6
In this lesson we did direct proofs
Sum of two odd numbers is even
$(2n+1)+(2m+1)=2(m+n+1)$

Then he proves the formula for sum of first $n$ terms
$S=1+2+3+\cdots+(n-1)+n$
$S=n+(n-1)+\cdots+3+2+1$
Adding both we get
$2S=\underbrace{(n+1)+(n+1)+\cdots+(n+1)}_{\text{n terms}}$
$2S = n(n+1)$
$S=\frac{n(n+1)}{2}$

Then he proves the transitivity formuala
$a|b, b|c \Rightarrow a|c$
$b=k_1a,c=k_2b$
Replacing $b$ we get
$c=k_2(k_1a)$
$c=(k_2k_1)a$
Thus we proved $a|c$

The next proof is to show that $\frac{a+b}{2}$ lies between $a$ and $b$ .

Last proof was to show $(a+b)^2 \ge 4ab$
We start with $(a-b)^2 \ge 0$
$a^2-2ab+b^2 \ge 0$
$a^2+b^2\ge 2ab$
$a^2+b^2+2av \ge 2ab+2ab$
$(a+b)^2 \ge 4ab$

Lecture 5
Negate the following two statements.
Everybody in the class likes Ice cream.
Somebody in the class didn’t do the homework.
There are two Quantifiers $\forall$ and $\exists$

There exists a red car in the parking lot.
There exists
Let $f$ be a polynomial. By IVT
$\exists x, 2x-6=0$

$\forall x,x^2 \ge 0$ . It’s a true statement.
$\forall x,\sqrt{x^2}=x$ . It’s a false statement.

All the cars in the parking lot are blue.
All the students in my class are boys.

Involving both quantifiers
For all real numbers $x$ , there exists a real number $y$ such that $y > x$ . True

For all positive real numbers $x$ there exists a positive real number $y$ , such that $y < x$ . True

Sequence: Sequence is a string of numbers.
$\{1,2,3,4,5,\cdots \}$
$\{1,-1,1,-1,1,-1,\cdots \}$
$\{1,1,2,3,5,8,13,21,24,45,55,\cdots \}$
There are two levels of understanding of Sequences.

Lecture 4

Lecture 3

Lecture 2

Lecture 1

	Sumant Sumant on A Geometry problem solved usin…
	sajithaa84a66b60d2 on A Geometry problem solved usin…
	Sumant Sumant on Angles between the diagonals o…
	pherlop300 on Evaporating water from a hemis…
	disho74 on IB SL Find the least positive…

How to Prove it

About Sumant Sumant

Leave a comment Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta

How to Prove it

Share this:

Related

About Sumant Sumant

Leave a comment Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta