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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If we have a recurrence like $$f(x)=af(\alpha x)+bf(\beta x)+g(x)$$ where $a,b,\alpha,\beta\in\mathbb{R}$ and $\alpha\neq\beta$ and $g(x)$ is known.

How can we solve this kind of recurrence?

For example, if we have $$f(x)=x+f\left(\frac{x}{2}\right)+f(2x)$$ and $f(1)=1$, $f(2)=1$. What is the general way that we can obtain $$f(x)=-\frac{2}{3}x+\frac{5}{3}\cos(\frac{\pi\ln x}{3\ln2})+\sqrt{3}\sin(\frac{\pi\ln x}{3\ln2})$$

share|cite|improve this question
you specify $a \neq b$, but in your example you have $a=b=1$. – Logan Stokols Nov 2 '12 at 10:17
But that's actually the difficulty there, because you can never solve the recurrence function $f(x)$ by trying to do direct computation. However, if you try my equation, you can see that is actually the solution which gives the exact value which you can never guess from the original recurrence. That's why I ask whether can we find algorithm to produce the answer given the recurrence. – user46090 Nov 2 '12 at 12:30
@user46090: Interesting problem. Could you give the source where this came from? – Matt Groff Nov 6 '12 at 1:33
@Matt Groff: I saw a problem to let you find the asymptotic behavior for such kind of equation on the web. So I solved the exact form as I described in the problem, and I want to see if there exists some general algorithm. – user46090 Nov 9 '12 at 9:16
up vote 2 down vote accepted

Case $1$: $a,b\neq0$ and $\alpha,\beta\in\mathbb{R}^+$

Let $\begin{cases}t=\log_nx\\F(t)=f(x)\end{cases}$ , $n\in\mathbb{R}^+\setminus\{1\}$ ,

Then $F(t)=aF(t+\log_n\alpha)+bF(t+\log_n\beta)+g(n^t)$


Let $\alpha=n^{k_1}$ and $\beta=n^{k_2}$ ,

Then $F(t)-aF(t+k_1)-bF(t+k_2)=g(n^t)$

If $k_1,k_2\in\mathbb{Z}$ , this is a difference equation

Its characteristic equation is $\lambda^{-\min\left(\frac{k_1}{\gcd(|k_1|,|k_2|)},\frac{k_2}{\gcd(|k_1|,|k_2|)},~0\right)}-a\lambda^{\frac{k_1}{\gcd(|k_1|,|k_2|)}-\min\left(\frac{k_1}{\gcd(|k_1|,|k_2|)},\frac{k_2}{\gcd(|k_1|,|k_2|)},~0\right)}-b\lambda^{\frac{k_2}{\gcd(|k_1|,|k_2|)}-\min\left(\frac{k_1}{\gcd(|k_1|,|k_2|)},\frac{k_2}{\gcd(|k_1|,|k_2|)},~0\right)}=0$

So its general solution is of the form $F(t)=\sum\limits_{k=1}^{\max\left(\frac{k_1}{\gcd(|k_1|,|k_2|)},\frac{k_2}{\gcd(|k_1|,|k_2|)},~0\right)-\min\left(\frac{k_1}{\gcd(|k_1|,|k_2|)},\frac{k_2}{\gcd(|k_1|,|k_2|)},~0\right)}\Theta_k(t)\lambda_k^t+F_p(t)~,$

where $\lambda_k$ are roots of $\lambda^{-\min\left(\frac{k_1}{\gcd(|k_1|,|k_2|)},\frac{k_2}{\gcd(|k_1|,|k_2|)},~0\right)}-a\lambda^{\frac{k_1}{\gcd(|k_1|,|k_2|)}-\min\left(\frac{k_1}{\gcd(|k_1|,|k_2|)},\frac{k_2}{\gcd(|k_1|,|k_2|)},~0\right)}-b\lambda^{\frac{k_2}{\gcd(|k_1|,|k_2|)}-\min\left(\frac{k_1}{\gcd(|k_1|,|k_2|)},\frac{k_2}{\gcd(|k_1|,|k_2|)},~0\right)}=0$ and $\Theta_k(t)$ are arbitrary periodic functions with period $\gcd(|k_1|,|k_2|)$

i.e. $f(x)=\sum\limits_{k=1}^{\max\left(\frac{k_1}{\gcd(|k_1|,|k_2|)},\frac{k_2}{\gcd(|k_1|,|k_2|)},~0\right)-\min\left(\frac{k_1}{\gcd(|k_1|,|k_2|)},\frac{k_2}{\gcd(|k_1|,|k_2|)},~0\right)}\Theta_k(\log_nx)\lambda_k^{\log_nx}+F_p(\log_nx)~,$

where $\lambda_k$ are roots of $\lambda^{-\min\left(\frac{k_1}{\gcd(|k_1|,|k_2|)},\frac{k_2}{\gcd(|k_1|,|k_2|)},~0\right)}-a\lambda^{\frac{k_1}{\gcd(|k_1|,|k_2|)}-\min\left(\frac{k_1}{\gcd(|k_1|,|k_2|)},\frac{k_2}{\gcd(|k_1|,|k_2|)},~0\right)}-b\lambda^{\frac{k_2}{\gcd(|k_1|,|k_2|)}-\min\left(\frac{k_1}{\gcd(|k_1|,|k_2|)},\frac{k_2}{\gcd(|k_1|,|k_2|)},~0\right)}=0$ and $\Theta_k(x)$ are arbitrary periodic functions with period $\gcd(|k_1|,|k_2|)$

$F_p(t)$ and $F_p(\log_nx)$ are their particular solution respectively. They can be found by method of undetermined coefficients if either of the form is obvious or by variation of parameter if both of the form are not obvious.

Other cases, i.e. either $k_1\notin\mathbb{Z}$ or $k_2\notin\mathbb{Z}$ , this is not a difference equation, even its form of general solution we have no concept on it

Case $2$: $a,b\neq0$ and either $\alpha\in\mathbb{R}^-$ or $\beta\in\mathbb{R}^-$

even its form of general solution we have no concept on it

share|cite|improve this answer
Your answer is very nice, but I can't read the latex. Could you edit it to displaystyle – yiyi Nov 9 '12 at 5:01
@MaoYiyi: But for this answer, edit it to displaystyle will even get worser. – doraemonpaul Nov 16 '12 at 7:56
I can't read the gcd very well, its a nice answer. – yiyi Nov 16 '12 at 8:14

Switch to $y=\log x$. You'll get $f*\mu=g$ where $\mu$ is some finite discrete measure. The solutions of the homogeneous equation are the closed linear span (in $C(\mathbb R)$) of exponential polynomials corresponding to the (complex) zeroes of $\widehat\mu$. The non-homogeneous case is somewhat uglier though sometimes you can get away with solving $\widehat f\widehat\mu=\widehat g$ by simple division. There solution you quoted can be obtained by choosing a few zeroes to have enough free parameters and solving the linear system that arises.

share|cite|improve this answer

Your Answer


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.