Functional Equations & Recurrences

$f(x) + 2f(1 - x) = 3x$: substitute $x \to 1 - x$ and solve the $2\times2$ system — $f(x) = 2 - 3x$. $f(x) + 2f(\tfrac1x) = 3x$: substitute $x \to \tfrac1x$ — $f(x) = \tfrac2x - x$. Always VERIFY the candidate in the original equation; the elimination only shows that IF a solution exists it has this form.

On $\mathbb Q$: $f(n) = nf(1)$ by induction, then $f(\tfrac pq) = \tfrac pqf(1)$ by $qf(\tfrac pq) = f(p)$ — so $f(1) = 7$ gives $f(\tfrac37) = 3$. A functional equation with an extra term ($f(x+y) = f(x) + f(y) + xy$) is Cauchy after subtracting a particular solution ($\tfrac{x^2}{2}$). Multiplicative equations: $f(12) = f(2)^2f(3)$ when the equation holds for ALL pairs.

Equations like $f(f(x)) = x$ (involutions), $f(x + 1) = -f(x)$ (period $2$), or $f(x+a) = \tfrac{1 + f(x)}{1 - f(x)}$ (a tangent-addition disguise, period $4a$) are solved by computing a few iterates. Fixed points constrain everything: if $f(f(x)) = x$ and $f$ is continuous and increasing then $f(x) = x$. For recurrences $a_{n+1} = g(a_n)$, the fixed points of $g$ and the sign of $g'$ there decide convergence.

$f(0) = 2f(0)$ gives $f(0) = 0$; $f(-x) = -f(x)$ from $f(x) + f(-x) = f(0)$. Induction gives $f(nx) = nf(x)$ for positive integers $n$, hence for all integers. For $x = \tfrac pq$: $qf(\tfrac pq) = f(p) = pf(1)$, so $f(\tfrac pq) = \tfrac pqf(1)$. $\blacksquare$ Significance: extending to $\mathbb R$ needs a regularity hypothesis — continuity at one point, monotonicity, or boundedness on an interval — and without it there are wild solutions (a Hamel basis). A Putnam solution must name which hypothesis it uses.

Suppose $f(a) > a$ for some $a$. Apply the increasing $f$: $f(f(a)) > f(a)$, i.e. $a > f(a)$ — contradiction. Symmetrically $f(a) < a$ is impossible. $\blacksquare$ Significance: monotonicity plus an involution equation collapses to the identity — the reason problems with $f(f(x)) = x$ always specify "decreasing" or drop monotonicity when they want interesting solutions like $f(x) = \tfrac1x$ or $c - x$.

Step 1 — fixed points of $g(x) = \sqrt{2 + x}$: $x^2 = 2 + x$ gives $x = 2$ (the positive root).

Step 2 — monotone and bounded: by induction $a_n < 2$ (since $a_n < 2 \Rightarrow a_{n+1} < \sqrt4 = 2$) and $a_{n+1} > a_n$ (since $\sqrt{2 + a} > a$ iff $a^2 - a - 2 < 0$ iff $a < 2$).

Step 3 — the monotone convergence theorem gives a limit $L$, and continuity of $g$ gives $L = g(L)$, so $L = 2$.

Step 4 — rate: $g'(2) = \tfrac14$, so the error shrinks by a factor of $4$ per step — a contraction, which is the general convergence criterion.

Step 1 — guess the particular solution from the extra term: $x^2$ satisfies $(x+y)^2 = x^2 + y^2 + 2xy$.

Step 2 — set $g(x) = f(x) - x^2$; then $g(x + y) = g(x) + g(y)$: Cauchy on $\mathbb Q$, so $g(x) = cx$ with $c = g(1) = f(1) - 1 = 2$.

Step 3 — $f(x) = x^2 + 2x$.

Step 4 — verify: $(x+y)^2 + 2(x+y) = x^2 + 2x + y^2 + 2y + 2xy$ ✓, and $f(1) = 3$ ✓. Subtracting a particular solution to reach Cauchy is the standard reduction.

Step 1 — $x = 0$ gives $f(0) = 2f(0)$, so $f(0) = 0$.

Step 2 — for $x \ne 0$ and every $n$, applying the equation $n$ times gives $f(x) = 2^nf\!\left(\tfrac{x}{2^n}\right) = x\cdot\dfrac{f(x/2^n) - f(0)}{x/2^n}$.

Step 3 — as $n \to \infty$, $\tfrac{x}{2^n} \to 0$, and the difference quotient tends to $f'(0)$ because $f$ is differentiable at $0$. The left side does not depend on $n$, so $f(x) = xf'(0)$. With $c = f'(0)$, $f(x) = cx$ for all $x$, and such $f$ clearly work. $\blacksquare$ The hypothesis cannot be dropped: $f(x) = x\sin(2\pi\log_2|x|)$ (with $f(0) = 0$) satisfies $f(2x) = 2f(x)$, is continuous, and is not linear — it is not differentiable at $0$.

How to find it. The equation relates $x$ to $2x$; iterate it in the direction that approaches the one point where a hypothesis is given (here $0$), and recognize the result as a difference quotient.