# How to prove $f(n) := \frac{1}{2}(a+(f(n-1))^2) ≤ 1-\sqrt{1-a}$

$a \in [0,1]\hspace{2em}f(1) := 0,\hspace{1em} f(n + 1) := \frac{1}{2}(a+(f(n))^2),\hspace{2em} n \in \mathbb{N}$

Prove:

$f(n) ≤ 1-\sqrt{1-a}$

I assume that I'll need to convert this recursive function to a non-recursive one in order to prove the inequation.

I've already calculated the values for 2 to 4:

$\hspace{2em}f(2) = \frac{1}{2}a$

$\hspace{2em}f(3) = \frac{1}{8}a^2 + \frac{1}{2}a$

$\hspace{2em}f(4) = \frac{1}{128}a^4 + \frac{1}{16}a^3 + \frac{1}{8}a^2 + \frac{1}{2}a$

I can see the regularity, but I don't know how to express it with what I learned so far.

-
Use induction. The statement is true for $n=0$, since $f(1)=0\leq 1-\sqrt{1-a}$ since $a\in [0,1]$. Now if the statement is true for $n-1$, that is, $f(n-1)\leq 1-\sqrt{1-a}$, then by definition $$f(n)=\frac{1}{2}(a+f(n-1)^2)\leq \frac{1}{2}(a+(1-\sqrt{1-a})^2)=\frac{1}{2}(a+1+(1-a)-2\sqrt{1-a})=1-\sqrt{1-a}.$$
@mcb: it comes from the left side of $\le$, which comes from the question –  Henry Nov 15 '11 at 0:36
@mcb: By the induction assumption, we have $f(n-1)\leq 1-\sqrt{a-1}.$ Taking square on both sides, we get $f(n-1)^2\leq (1-\sqrt{a-1})^2$. Now by definition, we know that $f(n)=\frac{1}{2}(1+f(n-1)^2)$. Therefore, if we substitute the above inequality of $f(n-1)$ into the formula of $f(n)$, we obtain $f(n)=\frac{1}{2}(1+f(n-1)^2)\leq\frac{1}{2}(1+(1-\sqrt{a-1})^2)$. That's where the $\frac{1}{2}$ comes from. –  Paul Nov 16 '11 at 8:15