Math Olympiad Question: Sum of powers of two

Is there a number that is a sum of two powers of 2, and ends with 3 zeros?

The answer is yes!

For example, $2^3+2^{253}$ =14474011154664524427946373126085988481658748083205070504932198000989141205000

How about n zeroes?

Check out last month’s problem of the month at: http://www.fen.bilkent.edu.tr/~cvmath/Problem/problem.htm

Question: http://www.fen.bilkent.edu.tr/~cvmath/Problem/1409q.pdf

Solution: http://www.fen.bilkent.edu.tr/~cvmath/Problem/1410a.pdf

Featured book:

104 Number Theory Problems: From the Training of the USA IMO Team

This challenging problem book by renowned US Olympiad coaches, mathematics teachers, and researchers develops a multitude of problem-solving skills needed to excel in mathematical contests and in mathematical research in number theory. Offering inspiration and intellectual delight, the problems throughout the book encourage students to express their ideas in writing to explain how they conceive problems, what conjectures they make, and what conclusions they reach. Applying specific techniques and strategies, readers will acquire a solid understanding of the fundamental concepts and ideas of number theory.

Fibonacci Numbers and the Mysterious Golden Ratio

What are Fibonacci Numbers?

Fibonacci Numbers, named after Leonardo Fibonacci, is a sequence of numbers:

$F_0=0, F_1=1, F_2=1, F_3=2, F_4=3, F_5=5$ ,

with a recurrence relation $F_n=F_{n-1}+F_{n-2}$ .

Relation to Golden Ratio

Fibonacci Numbers are linked to the mysterious Golden Ratio, $\displaystyle \phi=\frac{1+\sqrt{5}}{2}\approx 1.61803$

In fact, the ratio of successive Fibonacci numbers converges to the Golden Ratio! The first person to observe this is Johannes Kepler.

How do we prove it?

Recall the recurrence relation: $F_n=F_{n-1}+F_{n-2}$

Dividing throughout by $F_{n-1}$ , we get $\displaystyle \frac{F_n}{F_{n-1}}=1+\frac{F_{n-2}}{F_{n-1}}$

(We will first assume $\displaystyle\lim_{n\to\infty}\frac{F_n}{F_{n-1}}$ exists for the time being, and prove it later)

Taking limits, we get $\displaystyle\lim_{n\to\infty}\frac{F_n}{F_{n-1}}=1+\lim_{n\to\infty}\frac{F_{n-2}}{F_{n-1}}$ .

Denoting $\displaystyle\lim_{n\to\infty}\frac{F_n}{F_{n-1}}$ as $\phi$ , we get:

$\displaystyle \phi=1+\frac{1}{\phi}$

Multiplying by $\phi$ , we get $\phi^2=\phi +1$

$\phi^2-\phi-1=0$

This is a quadratic equation, solving using the quadratic equation, we get:

$\displaystyle \phi=\frac{1\pm\sqrt{1^2-4(1)(-1)}}{2}=\frac{1\pm\sqrt{5}}{2}$

Since $\phi$ is clearly positive, we have $\displaystyle \phi=\frac{1+\sqrt{5}}{2}$ which is the Golden Ratio!

For a complete proof, actually we will need to prove that $\displaystyle\frac{F_n}{F_{n-1}}$ converges. This is a bit tricky and requires some algebra.

Interested readers can refer to the excellent website at: http://pages.pacificcoast.net/~cazelais/222/fib-limit.pdf

for more details.

Interesting video on Fibonacci numbers!

http://www.youtube.com/watch?v=dsomgrotZUg

Fibonacci numbers and the Golden Ratio can also be used for trading stocks.

Paul Erdos’ Proof that there are Infinite Primes

Paul Erdos’ Proof that there are Infinite Primes (with Examples)

Every integer can be uniquely written as $rs^2$ , where $r$ is square-free (not divisible by any square numbers). For instance, 6 is square-free but 18 is not, since 18 can be divided by $3^2$ .

We can do this by letting $s^2$ to be the largest square number that divides $n$ , and then let $r=n/s^2$ . For instance, if $n=108$ , $6^2$ is the largest square number that divides 108, so we let $r=108/6^2 = 3$ .

Now, suppose to the contrary that a finite number k of prime numbers exists. We fix a positive integer $N$ , and try to over-estimate the number of integers between 1 and $N$ . Using our previous argument, each of these numbers can be written as $rs^2$ , where $r$ is square-free and $r$ and $s^2$ are both less than $N$ .

By the fundamental theorem of arithmetic, there are only $2^k$ square free numbers. (The number of subsets of a set with k elements is 2^k) Since $s^2<N$ , we have $s<\sqrt{N}$ .