3

A function $f(n)$ is defined for $n=4^k$, $k\geq0$. $f(n)$ is given in a recursion format:

$$ f(n)= \begin{cases} &3f(\frac{n}{4})-2f(\frac{n}{16})+\frac{3}{8}n,\quad n\geq160 \\ &1,\quad n=1 \\ &3,\quad n=4 \end{cases} $$

I need to prove in a typical equation method only, that $f(n)=n-\sqrt{n}+1 $ is exist.

Now, I have tried this way:

1) $n=4^k$

$$ f(4^k)=3f(4^{k-1})-2f(4^{k-2})+\frac{3}{8}4^k $$

2) $ f(4^k)=g(k) $ for $ k\geq0 $

$$ g(k)=3g(k-1)-2g(k-2)+\frac{3}{8}4^k $$

$$ g(0)=1, g(1)=3 $$

3) Divide by $ 4^k $ and define $ h(k)=\frac{g(k)}{4^k} $

$$ h(k)=\frac{3}{4}h(k-1)-\frac{1}{8}h(k-2)+\frac{3}{8} $$

And this is where I get stack, I realy don't know if I did right or how to keep forward..

Please, HELP ?

Thanks!

user12499410
  • 183
  • 4
    If $f(n)$ is defined for $n=4^k$, wouldn't it be easier to define $a_k:=f(4^k)$ for each integer $k\geq 0$? In this way, you have $a_0=1$, $a_1=3$, and $$a_k=3,a_{k-1} -2,a_{k-2}+\frac{3}{8}\cdot 4^k$$ for all integers $k\geq 2$. A particular solution $a_k^{(p)}$ is $$a_k^{(p)}=4^k$$ for all $k=0,1,2,\ldots$. – Batominovski May 02 '20 at 17:34
  • I did as you suggested, very helpfull, but I still need to prove that $f(n)=n-\sqrt{n}+1$ is the solution for the recursion $f(n)$ .. ?! – user12499410 May 02 '20 at 22:55
  • Which formula did you obtain for $a_k$? – Batominovski May 02 '20 at 22:58
  • @Batominovski see edit – user12499410 May 02 '20 at 23:21
  • 1
    When you divided the equation by $4^k$, the recurrence relation for $h(k)$ is not what you wrote. It is $$h(k)=\frac34,h(k-1)-\frac18,h(k-2)+\frac38,.$$ – Batominovski May 03 '20 at 06:32
  • @Batominovski you are right! edited .. – user12499410 May 03 '20 at 11:47
  • (1) You should find out how to solve recurrence relations. What you got for $h(k)$ can be solved using a standard technique. Look online. In this site, there are many old examples you can take a look. $$\phantom{a}$$ (2) That said, you are unnecessarily complicating your solution. If you had just taken my suggestion by solving for $a_k$, the solution would be more straightforward. After all, I already told you what a particular solution $a_k^{(p)}$ looks like. – Batominovski May 03 '20 at 13:39

0 Answers0