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.

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

share|improve this question
1  
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$? –  alex.jordan Oct 19 '12 at 7:12
    
@alex.jordan You're right. Fixed. –  Mike Izbicki Oct 19 '12 at 16:03
    
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... –  Matt Groff Oct 21 '12 at 22:52

1 Answer 1

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

share|improve this answer
    
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. –  Mike Izbicki Oct 19 '12 at 16:41

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.