1
$\begingroup$

a function $f$ satisfies the following conditions:

$$\begin{align*} &f(1)=1\\ &f(n)=f(n-1)+2\sqrt{f(n-1)}+1\quad\text{for integers}\quad n\ge 2 \end{align*}$$

Find a formula that might be true for all integers $n\ge1$. Then prove using mathematical induction that it is indeed correct.

I found that the formula is $f(n)=n^2$, but I'm stuck on how to prove it... can anyone help me please?

Thanks a lot!

$\endgroup$
  • 1
    $\begingroup$ It may or may not help to rewrite the recursion as $f(n)=(\sqrt{f(n-1)}+1)^2$ $\endgroup$ – Mike Oct 30 '12 at 0:57
  • $\begingroup$ ok thanks guys, I messed myself up with this recursion lol $\endgroup$ – Saitama Oct 30 '12 at 0:58
1
$\begingroup$

HINT for the induction step: if $f(n)=n^2$, then $$f(n+1)=f(n)+2\sqrt{f(n)}-1=n^2+2\sqrt{n^2}+1=\dots~?$$

$\endgroup$
1
$\begingroup$

Hint: you already have the base case. All you have to do is to use the induction hypothesis which is $f(n-1)=(n-1)^2$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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