2
$\begingroup$

I have the following equation: $$ h(n) = n \sum_{i=0}^{\lceil \log_2 n \rceil} \frac{m(2^i)}{2^i} $$

and I'm trying to understand exactly the relationship between the functions $h$ and $m$. The easiest way for me to do this is to fix $m$ to some specific function, then try to figure out what $h$ is. For example:

\begin{align} m(n) &= 1 &\Rightarrow h(n) &= n \\ m(n) &= \log n &\Rightarrow h(n) &= n\\ m(n) &= n &\Rightarrow h(n) &= n \log n \\ m(n) &= n^2 &\Rightarrow h(n) &= 2^n \end{align}

It would be really helpful, however, to be able to fix $h$ and find the cooresponding value of $m$. For example, what is $m$ if $h(n)=n^2$?

Is there some general procedure for doing this? Am I even approaching this problem in the right way?


Edit: In particular, I'd especially like to find out what $h$ and $m$ are equal to when $h(n) = m(n)$.

$\endgroup$
3
  • 1
    $\begingroup$ There's a variable $x$ on your left hand side that is nowhere on the right, so I don't follow you from line 1. Is that $x$ supposed to be $n$? $\endgroup$
    – 2'5 9'2
    Oct 19, 2012 at 7:12
  • $\begingroup$ @alex.jordan You're right. Fixed. $\endgroup$ Oct 19, 2012 at 16:03
  • $\begingroup$ This seems to me to be a problem that "$\textit{difference}$ equations" (not to be confused with $\textit{differential}$ equations) and the "difference calculus" can solve. You can look for the phrases in quotes to get more information. Essentially, You apply the difference delta to both sides (to get $\Delta h(n)=\Delta n f(m,n)$). Then solve the corresponding difference equation. I'll see if I can come up with a generalized procedure for doing this, or at least a specific example... $\endgroup$
    – Matt Groff
    Oct 21, 2012 at 22:52

1 Answer 1

1
$\begingroup$

If $h(n)$ identically equals $$n\sum_{n=0}^{\lceil\log_2n\rceil}\frac{h(2^i)}{2^i}$$ then $h$ must be the zero function on positive integer $n$.

To begin,

$$\begin{align} h(2) & =2\sum_{i=0}^1\frac{h(2^i)}{2^i}\\ h(2) &=2\left(h(1)+\frac{h(2)}{2}\right)\\ h(2) &=2h(1)+h(2)\\ \end{align}$$

So $h(1)=0$. Now inductively assume that $h(2^k)=0$ for all nonnegative integer $k$ up to $K$. (We have established this for $K=0$.) Then

$$\begin{align} h(2^{K+2})&=2^{K+2}\sum_{n=0}^{K+2}\frac{h(2^i)}{2^i}\\ &=2^{K+2}\sum_{n=K+1}^{K+2}\frac{h(2^i)}{2^i}\\ &=2^{K+2}\left(\frac{h(2^{K+1})}{2^{K+1}}+\frac{h(2^{K+2})}{2^{K+2}}\right)\\ &=2h(2^{K+1})+h(2^{K+2}) \end{align}$$

implying $h(2^{K+1})=0$. So by induction, $h$ is zero on all powers of $2$. Since $h(n)$ is a linear combination of $h(2^k)$, $h(n)=0$ for all $n$.

$\endgroup$
1
  • $\begingroup$ Doh. That should have been obvious to me, thanks. I'm still not quite sure how to go about understanding the relationship when they're not both zero. $\endgroup$ Oct 19, 2012 at 16:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .