3
$\begingroup$

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

  • 0
    you specify $a \neq b$, but in your example you have $a=b=1$.2012-11-02
  • 0
    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.2012-11-02
  • 1
    @user46090: Interesting problem. Could you give the source where this came from?2012-11-06
  • 0
    @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.2012-11-09

2 Answers 2

2

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

$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

  • 0
    Your answer is very nice, but I can't read the latex. Could you edit it to displaystyle2012-11-09
  • 0
    @MaoYiyi: But for this answer, edit it to displaystyle will even get worser.2012-11-16
  • 0
    I can't read the gcd very well, its a nice answer.2012-11-16
1

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.