$\left[\begin{array}{l}{[\text { Generating functions }} \\ {[\text { Recurrence relations (other) }}\end{array}\right]$ |  |
| :---: | :---: |
|  |  |

a) Find the generating function for the sequence of Lucas numbers (the definition of Lucas numbers see in problem $60585$).

b) Using this function, express $L_{n}$ in terms of $\varphi$ and $\hat{\varphi}$ (see problem $\left.\underline{61502}\right)$).
a) According to problem $\underline{60498}$, the generating function $F(x)$ of the Fibonacci sequence is $\frac{x}{1-x-x^{2}}$.

According to problem $\underline{60585}$ a) $L_{n}=F_{n+1}+F_{n-1}$, thus,

$$
L(x)=1+x^{-1} F(x)+x F(x)=1+\frac{1+x^{2}}{x} \cdot \frac{x}{1-x-x^{2}}=\frac{2-x}{1-x-x^{2}}
$$

b) Notice that $\frac{1}{1-\varphi x}+\frac{1}{1-\widehat{\varphi} x}=\frac{2-(\varphi+\widehat{\varphi}) x}{(1-\varphi x)(1-\widehat{\varphi} x)}=\frac{2-x}{(1-\varphi x)(1-\widehat{\varphi} x)}$. Therefore,

$$
L(x)=\frac{1}{1-\varphi x}+\frac{1}{1-\widehat{\varphi} x}, \quad \frac{L^{(n)}(x)}{n!}=\frac{\varphi^{n}}{(1-\varphi x)^{n}}+\frac{\widehat{\varphi}^{n}}{(1-\widehat{\varphi} x)^{n}}, L_{n}=\frac{L^{(n)}(0)}{n!}=\varphi^{n}+\widehat{\varphi}^{n}
$$

## Answer

a) $L(x)=(2-x)\left(1-x-x^{2}\right)^{-1}$; b) $L_{n}=\varphi^{n}+\widehat{\varphi}^{n}$.

## Ptolemy's Theorem  Classical Inequalities (Miscellaneous).

Author: $\underline{\text { Folklore }}$

Prove that for any four points $A, B, C, D$, not lying in the same plane, the inequality $A B \cdot C D+A C \cdot B D>A D \cdot B C$ holds.

## Solution

Let $D^{\prime}$ be the projection of point $D$ onto the plane $A B C$. Denote $a=B C, b=A C, c=A B, d=D D^{\prime}, u=A D^{\prime}, v=$ $B D^{\prime}, w=C D^{\prime}$. We need to prove the inequality $c \sqrt{w^{2}+d^{2}}+b \sqrt{v^{2}+d^{2}}>a \sqrt{u^{2}+d^{2}}$. After squaring, we get

$$
c^{2} w^{2}+b^{2} v^{2}+2 b c \sqrt{w^{2}+d^{2}} \cdot \sqrt{v^{2}+d^{2}}+\left(c^{2}+b^{2}\right) d^{2}>a^{2} u^{2}+a^{2} d^{2}
$$

According to Ptolemy's inequality for points on a plane (see problem 58396 a) $c w+b v \geq a u$, that is, $c^{2} w^{2}+b^{2} v^{2}+$ $2 b c v w \geq a^{2} u^{2}$. According to the triangle inequality $c+b>a$, that is, $c^{2}+b^{2}+2 b c>a^{2}$. Therefore, it is sufficient to prove that $\sqrt{w^{2}+d^{2}} \cdot \sqrt{v^{2}+d^{2}} \geq v w+d^{2}$. But this is a special case of the Cauchy-Bunyakovsky inequality (see problem $\underline{61402}$ a).