FIbonacci criteria

 Show that $F$ is a fibonacci number if and only if $5F^2 \pm 4$ is a perfect square.

i.e if one of $5F^2 + 4$ or $5F^2 - 4$ is a perfect square, then $F$ is fibonacci and vice-versa.

Surprising difference of cube roots

 Show that

$$\sqrt[3]{10 + \sqrt{108}} - \sqrt[3]{\sqrt{108} - 10}$$

is an integer.

Solution below.

.

.

If $a = \sqrt[3]{10 + \sqrt{108}}$ and $b = \sqrt[3]{\sqrt{108} - 10}$

Then we have that $ab = 2$ and $a^3 - b^3 = 20$.

By binomial theorem we also have $$(a-b)^3 = a^3 - b^3 - 3ab(a-b)$$

Thus the given expression ($a - b$) is a root of

$$t^3 + 6t - 20$$

$t = 2$ is the only real root.

A proof of Pythagoras Theorem

Here is a potentially new proof of the Pythagoras theorem I discovered recently. I could not find any prior proofs like these (including in the cut-the-knot pythagorean proof dump), so if you have seen it somewhere, please let me know.

ABC is the right triangle with sides a,b,c.

AD is the angular bisector of CAB and DE is the perpendicular from D to AB.

CD = x, DB = a-x.

It is easily seen that triangles ACD and ADE are congruent and so AE = AC = b and BE = c-b

Area of ACD + Area of ADB = Area of ABC gives

$bx + cx = ab $

And so $x = ab/(b+c)$

Now triangles DEB and ABC are similar and so

$$DE/AC = BE/BC$$

i.e.

$$x/b = (c-b)/a$$

$$a/(b+c) =(c-b)/a$$

Which gives

$$ a^2 = c^2 - b^2$$

Base b and generating functions

 Not a puzzle, just a quick observation noting the power of generating functions.

Say $b \ge 2$ is a positive integer. We give a quick proof using generating functions that every positive integer can be written uniquely in base $b$ with digits $0, 1, \dots, b-1$.

Let $n \ge 1$. Consider 

$$ G(x) = \prod_{k=0}^{n} (1 + x^{b^k} + x^{2b^k} + \dots + x^{(b-1)b^k})$$

Observe that the coefficient of $x^N$ shows the numbers of ways of writing $N$ is base $b$.

Now if $u = x^{b^k}$, then

$$ (1 + x^{b^k} + x^{2b^k} + \dots + x^{(b-1)b^k}) = (1 + u + u^2 + \dots u^{b-1})  = \frac {1 - u^b}{1-u}$$

Thus

$$G(x) = \frac{1-x^b}{1-x}\frac{1-x^{b^2}}{1-x^b}\frac{1-x^{b^3}}{1-x^{b^2}}\dots\frac{1-x^{b^{n+1}}}{1-x^{b^n}}$$

This telescopes to

$$ G(x) = \frac{1 - x^{b^{n+1}}}{1-x}$$

$$ = 1 + x + x^2 + \dots + x^{b^{n+1} - 1}$$

Thus every integer $N$ in the range $1$ to $b^{n+1} - 1$, can be written in base $b$ using at-most $n+1$ digits, taken from $0,1,2, \dots, b-1$. Since the coefficient of $x^N$ is $1$, the representation is unique.

A cute integral with golden ratio

 Show that

$$\int_{0}^{\infty} \frac{dx}{(1 + x^{\varphi})^{\varphi}} = 1$$

where $\varphi = \frac{\sqrt{5} + 1}{2}$ is the golden ratio.

Scroll down for solution:

Using the substitution $x^{-\varphi} = t$ and the identity $\varphi^2 = \varphi + 1$ we get that

$$dx = -\frac{1}{\varphi} t^{-\varphi} dt$$

Thus the integral becomes

$$\frac{1}{\varphi} \int_{0}^{\infty} \frac{dt}{(1 + t)^{\varphi}}$$

Which is easy to calculate.

A putnam sequence problem

 Let $a_n$ be a sequence such that

$$a_1 = a \ge 2$$

and

$$a_{n+1} = a_{n}^2 - 2$$

Show that 

$$\left(1 - \frac{1}{a_1}\right)\left(1 - \frac{1}{a_2}\right)\dots = \prod_{n \ge 1} \left(1 - \frac{1}{a_n}\right) = \frac{\sqrt{a^2 - 4}}{1 + a}$$

The putnam problem was with $a = \frac{5}{2}$

Scroll down for a solution.

Since $a \ge 2$, we can find a $u \ge 1$ such that $a = u + \frac{1}{u}$ (for $a = \frac{5}{2}, u =2$).

The case $a = 2, u = 1$ is easy, so assume $u \gt 1$.

The recurrence then gives us

$$a_{n+1} = u^{2^n} + \frac{1}{u^{2^n}}$$

Let $$f(x) = \left(1 - \frac{1}{x + \frac{1}{x}}\right) = \frac{x^2 - x + 1}{x^2 + 1}$$

The value we are seeking is

$$f(u)f(u^2)f(u^4)f(u^8)\dots f(u^{2^n})\dots$$

Now notice that

$$(x^2 - x + 1)(x^2 + x + 1) = (x^2 + 1)^2 - x^2 = x^4 + x^2 + 1$$

Thus if we multiply

$$(x^2 - x +1)(x^4 - x^2 + 1)(x^8 - x^4 + 1)\dots(x^{2^{n}} - x^{2^{n-1}} + 1) $$

with $x^2 + x + 1$ we get

$$(x^2 + x + 1)(x^2 - x +1)(x^4 - x^2 + 1)(x^8 - x^4 + 1)\dots(x^{2^{n}} - x^{2^{n-1}} + 1)  = $$

$$(x^4 + x^2 + 1)(x^4 - x^2 + 1)\dots(x^{2^{n}} - x^{2^{n-1}} + 1)  = x^{2^{n+1}} + x^{2^n} + 1$$

and similarly using 

$$(x^2 - 1)(x^2 + 1) = x^4 - 1$$

we get

$$(x^2 - 1)(x^2 + 1)(x^4 + 1) \dots (x^{2^n} + 1) = x^{2^{n+1}} - 1$$

Since

$$\frac{x^{2^{n+1}} + x^{2^n} + 1}{x^{2^{n+1}} - 1} \to 1$$

(for $x >1$)

We see that

$$L = f(u)f(u^2)\dots f(u^{2^n})\dots = \frac{u^2 - 1}{u^2 + u + 1}$$

This we can rewrite as

$$ L = \frac{u - \frac{1}{u}}{u + \frac{1}{u} + 1} $$

Squaring gives

$$L^2 = \frac{u^2 + \frac{1}{u^2} - 2}{(a+1)^2} = \frac{a^2 -4}{(a+1)^2}$$

Thus 

$$ L = \frac{\sqrt{a^2 - 4}}{a+1}$$

Solutions added

Finally added some solutions to the problems by updating the problem post itself. 

If there are any missing which you would like to see, please comment on the problem post.

A surprising expression with nested square roots

 Simplify 

$$ \frac{\sqrt{10 + \sqrt{1}} + \sqrt{10 + \sqrt{2}} + \dots + \sqrt{10 + \sqrt{99}}}{\sqrt{10 - \sqrt{1}} + \sqrt{10 - \sqrt{2}} + \dots + \sqrt{10 - \sqrt{99}}}$$

Scroll down for simplified form and solution.

The expression is equal to $\sqrt{2} + 1$.  Surprising!

Scroll down for solution.

Let $a + b $ = 100. 

Now

$$\sqrt{10 - \sqrt{a}} \sqrt{10 + \sqrt{a}} = \sqrt{100 - a}  = \sqrt{b}$$

Let $u = \sqrt{10 + \sqrt{a}}$ and $v = \sqrt{10 - \sqrt{a}}$

So $20 = u^2 + v^2$

and $\sqrt{b} = uv$

Thus

$$\sqrt{20 + 2\sqrt{b}} = \sqrt{u^2 + v^2 + 2uv} = u+v$$

Similarly

$$\sqrt{20 - 2\sqrt{b}} = \sqrt{u^2 + v^2 - 2uv} = u-v$$

Thus if 

$$P = \sum_{a=1}^{99} \sqrt{10 + \sqrt{a}}$$

and

$$Q = \sum_{a=1}^{99} \sqrt{10 - \sqrt{a}}$$

We get 

$$ \sqrt{2} P = P + Q$$ and

$$\sqrt{2} Q = P - Q$$

This gives us $$\frac{P}{Q} = \sqrt{2} + 1$$

Putnam 2012 B4 generalization

 Let $c \gt 0$ be a real number and $a_n$ be a sequence such that $a_0 = 1$ and $$a_{n+1} = a_n  + e^{-c a_n}$$

Show that

$$\lim_{n \to \infty} (ca_n - \log n) = \log c$$

($\log$ is $\log$ to base $e$)

The Putnam problem was with $c = 1$ and only asked for proof of existence of the limit.

Scroll down for a solution.

Consider $b_n = e^{a_n}$ then we get that $b_{0} = e$ and

$$ b_{n+1} = b_n e^{1/(b_n)^c}$$

We can easily show that $a_n$ is unbounded (proof by contradiction) and so is $b_n$ and thus $\frac{1}{b_{n}^c} \to 0$.

The recurrence for $a_n$ gives us

$$b_{n+1}^c = b_{n}^c e^{c/(b_n)^c}$$

Expanding the $e^{\dots}$ part we get

$$b_{n+1}^c = b_{n}^c ( 1 + \frac{c}{b_{n}^c} + O\left(\frac{1}{b_{n}^{2c}}\right)) = b_{n}^c + c + O\left(\frac{1}{b_{n}^c}\right)$$

This telescopes to give us

$$b_{n}^c - b_{0}^c = nc + \sum_{k=0}^{n} O\left(\frac{1}{b_{k}^c}\right)$$

And so

$$\frac{b_{n}^c - b_{0}^c}{n} = c + \frac{\sum_{k=0}^{n} O\left(\frac{1}{b_{k}^c}\right)}{n}$$

Thus

$$ \frac{b_{n}^c}{n} \to c$$

Taking logarithms gives the result.

A cute problem from New Zealand Maths Olympiad

 

In the image above, ABCD is a square, and BX = DY, X lying on BC, and Y on CD extended.

P is the intersection point of the diagonal BD and XY. 

Show that PY = PX. 

(Diagram not to scale!)

Try using pure geometric methods only.

Solution diagram below:

Nested square roots

Let $f(a)$ be the number of positive integers $x$ such that $$ \sqrt{x + \sqrt{x + a}}$$ is a positive integer. 

 Show that there are infinitely many positive integers $a$ such that $f(a) = 1$

Scroll down for a solution.

Note that for $x = a^2 - a$, $\sqrt{x + \sqrt{x+a}} = a$ is an integer for positive integer $a$ and thus $f(a) \ge 1$ for positive integer $a$.

Now suppose $$\sqrt{x + \sqrt{x+a}} = p$$

Some algebra gives us that 

$$x^2 - (2p^2+1)x + (p^4 - a) = 0$$

For this to have an integer solution we need the discriminant to be a perfect square. 

And so

$$(2p^2 + 1)^2 - 4(p^4 - a) = q^2$$

Which leads to

$$4a +1 = (q-2p)(q+2p)$$

Thus if $4a+1$ is prime, there is a unique solution.

Since there are infinitely many primes of the form $4a+1$, we are done.

An integral with a parameter.

The problem is to evaluate (with proof) $$f(a) = \int_{0}^{\infty} \frac{x^2}{(x^2 - a^2)^2 + x^2} \text{ d}x$$ where $a$ is a real number.


Scroll down for a solution.






Surprisingly, the answer is independent of $a$!.

For $a=0$, the integral is the standard $\int_{0}^{\infty} \frac{dx}{1+x^2} = \frac{\pi}{2}$. A valuable tool when evaluating integrals is substitution and it really helps here. First, assume $a \neq 0$, and make the substitution $u = \frac{a^2}{x}$ This gives us that $$f(a) = \int_{0}^{\infty} \frac{\frac{a^4}{u^2}}{((\frac{a^4}{u^2} - a^2)^2 + \frac{a^4}{u^2})} \frac{a^2\text{d}u}{u^2}$$ $$ = \int_{0}^{\infty} \frac{a^2}{(u^2 - a^2)^2 + u^2} \text{ d}u$$ $$ = \int_{0}^{\infty} \frac{a^2}{(x^2 - a^2)^2 + x^2} \text{ d}x$$ Thus by adding the original, we get that $$2f(a) = \int_{0}^{\infty} \frac{x^2 + a^2}{(x^2 - a^2)^2 + x^2} \text{ d}x$$ $$ = \int_{0}^{\infty} \frac{1 + \frac{a^2}{x^2}}{(x - \frac{a^2}{x})^2 + 1} \text{ d}x$$ Now make the substitution $u = x - \frac{a^2}{x}$ to get $$2f(a) = \int_{-\infty}^{\infty} \frac{1}{u^2 +1} \text{ d}u = \pi$$ And so $$\int_{0}^{\infty} \frac{x^2}{(x^2 - a^2)^2 + x^2} \text{ d}x = \frac{\pi}{2}$$ Note: The substitutions need to be justified because technically, the integral is an improper integral, but we leave that to the reader :)

Cute problem from IIT JEE

If $r,s,t$ are roots (you can assume they are all real) of $$x^3 + 3x^2 - 24x + 1 = 0$$ Find $$ \sqrt[3]{r} + \sqrt[3]{s} + \sqrt[3]{t}$$ If you know which year this is from, please let me know.

Scroll down for solution (and something extra).

Let $P(x) = x^3 + 3x^2 - 24x + 1$.

Note that $P(0) > 0, P(1) < 0$ and $P(24) > 0$ and so has at least two real roots. Which implies all roots are real, so we can freely take cube roots.

Now 

$$x^3 +3x^2 - 24x + 1 = x^3 + 3x^2 + 3x + 1 - 27x = (x+1)^3 - 27x$$.

Thus if $a$ is a root of $P$, then

$$ (a+1)^3 = 27a \implies 3a^{1/3} = (a + 1)$$

Thus the sum of cuberoots of P is $(r+s+t + 3)/3 = 0$.

For the extra:

We will in fact show that $\sqrt[3]{r},\sqrt[3]{s},\sqrt[3]{t}$ are roots of $x^3 - 3x + 1 = 0$.

Let $d=\sqrt[3]{r},e=\sqrt[3]{s},f=\sqrt[3]{t}$ be roots of $Q(x) = x^3 + ax^2 + bx + 1$

Thus $Q(x) = (x-d)(x-e)(x-f)$

Now if $w$ is a cuberoot of unity, then

$$Q(x)Q(wx)Q(w^2x) = (x^3 - d^3)(x^3-e^3)(x^3 - f^3) = P(x^3) = x^9 + 3x^6 -24x^3 + 1$$

With slightly tedious algebra, we see that

$$Q(x)Q(wx)Q(w^2x) = x^9 + (a^3 - 3ab + 3)x^6 + (b^3 - 3ab + 3)x^3 + 1$$

Thus we get

$$a^3 - 3ab = 0$$

$$b^3 - 3ab = -27$$ 

From the first equation either $a=0$ (in which case $b = -3$) or $a^2 = 3b$.

If $a \neq 0$, putting $b = a^2/3$ in the second results in a quadratic (in $a^3$) with complex roots. Since $a$ needs to be real (sum of real numbers) we see that $a = 0, b = -3$ and hence the cuberoots are roots of 

$$x^3 - 3x + 1 = 0$$

2 equations 3 variables

Given that $x, y, z$ are real, solve (with proof) the system of equations: $$ (x-1)(y-1)(z-1) = xyz - 1$$ $$ (x-2)(y-2)(z-2) = xyz - 2$$ part b) $x,y,z$ are allowed to be complex.

Scroll down for solution.

Let $$P(t) = (x-t)(y-t)(z-t)$$. $x,y,z$ are roots of $P(t) = 0$.

Expand and assume

$$P(t) = c - bt + at^2 - t^3$$

The two equations basically say

$$P(1) = c -1$$

and

$$P(2) = c -2$$

The first gives $a = b$

and second gives $2a - b = 3$ and thus $a=b = 3$

Thus $$P(t) = c - 3t + 3t^2 - t^3 = c -1 - (t^3 -3t^2 + 3t - 1) = (c-1) - (t-1)^3 $$

Thus $x,y,z$ are roots of 

$$(t-1)^3 = c-1$$

For $x,y,z$ to be real, we need $c=1$ and $x=y=z=1$.

If $x,y,z$ are allowed to be complex, pick a random $c$ and $x,y,z$ are $w\sqrt[3]{c-1}  + 1$ where $w$ are the three cuberoots of unity.