1
$\begingroup$

I was given the equation $a(4n) = {a(n)\over 4}$ where $a(1) = 1$. I know that ${1\over \sqrt n }$ solves this equation, but I don't know how I would find this solution by hand if I didn't know about it.
Any hints on this matter are greatly appreciated.
EDIT: oh snap I made a typo. It is $a(4n) = {a(n)\over 2}$. I apologize for my mistake.

I'm not sure why my question was put on hold. To clarify, I was asking how one would systematically solve the recursive equation given above, as I was only able to see the solution, but not how one would find it.
Anyway, my question has been answered by eranreches (do I need to something else apart from selecting the best answer to mark the question as answered? -- if I have to, I'm sorry, it is my first time posting here...)

$\endgroup$

closed as unclear what you're asking by Did, Claude Leibovici, Shaun, José Carlos Santos, Shailesh Dec 15 '17 at 0:11

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Welcome to MSE. Please read this text about how to ask a good question. $\endgroup$ – José Carlos Santos Dec 14 '17 at 10:50
  • $\begingroup$ What is the equation? $\endgroup$ – MathematicianByMistake Dec 14 '17 at 10:52
  • 1
    $\begingroup$ $\frac 1{\sqrt n}$ does not solve your recurrence. With that definition, $a_1=1$ but $a_4=\frac 12$. $\endgroup$ – lulu Dec 14 '17 at 10:55
  • 1
    $\begingroup$ @lulu Isn't $a_4 = 1/4$? $\endgroup$ – Yanko Dec 14 '17 at 10:58
  • 1
    $\begingroup$ Note that $a(n) = c/n$ is a solution. I found this by assuming that $a(n) = n^p$, and then solving $4^p = 1/4$. I'm not sure if this is the only solution, though. $\endgroup$ – JavaMan Dec 14 '17 at 11:57
0
$\begingroup$

If you want a more systematic way, define

$$b_{n}\equiv a_{4^{n}}$$

Then

$$b_{0}=a_{1}=1$$

$$b_{n+1}=a_{4^{n+1}}=a_{4\cdot4^{n}}=\frac{a_{4^{n}}}{2}=\frac{b_{n}}{2}$$

with a solution $b_{n}=\frac{1}{2^{n}}$. Now reverse to get

$$a_{n}=b_{\log_{4}n}=\frac{1}{2^{\log_{4}n}}=\frac{1}{4^{\frac{1}{2}\log_{4}n}}=\frac{1}{n^{\frac{1}{2}}}=\frac{1}{\sqrt{n}}$$

as wanted.

$\endgroup$
  • $\begingroup$ This is exactly what I was looking for. Thank you for your answer $\endgroup$ – loungelizard Dec 14 '17 at 14:43
1
$\begingroup$

Let $n=4^k$, so that $4n=4^{k+1}$, and let $b(k):=a(2^k)=a(n)$.

Now

$$b(k+1)=\frac{b(k)}2,$$ which is an ordinary recurrence, with the particular solution (fulfilling $b(0)=1$)

$$b(k)=\frac 1{2^k}=\frac 1{\sqrt n}=a(n).$$

$\endgroup$

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