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