# 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}.$$

-
I don't quite understand where this 1/2 is from on the right side of ≤. – user8823741 Nov 14 '11 at 22:48
@mcb: it comes from the left side of $\le$, which comes from the question – Henry Nov 15 '11 at 0:36
Can someone explain this step a bit more detailed? – user8823741 Nov 15 '11 at 19:53
@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
Thanks, that helped a lot! – user8823741 Nov 16 '11 at 17:08