Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


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

share|cite|improve this question
up vote 6 down vote accepted

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.