Take the 2-minute tour ×
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.

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

share|improve this question

1 Answer 1

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|improve this answer
    
I don't quite understand where this 1/2 is from on the right side of ≤. –  mcb Nov 14 '11 at 22:48
1  
@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? –  mcb Nov 15 '11 at 19:53
1  
@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! –  mcb Nov 16 '11 at 17:08

Your Answer

 
discard

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.