TITLE: Functional equation $f(x)=f(x-1)+f(x-a)$
QUESTION [1 upvotes]: Please help to solve functional equation for real numbers
We have:
$a\in \mathbb{R}$ and $a>1$
$f_a(x)=1$ if $x<a$
$f_a(x)=f_a(x-1)+f_a(x-a)$ for $x\ge a$
@update
Actually we have to find $f(n)$ in case $a=\sqrt n$, where $n$ is natural number.
So question is find $G(n)=f_{\sqrt n} (n)$ for $n \in \mathbb N$ and $n \ge 2$
$G(2)=2$
$G(3)=3$
$G(4)=5$
$G(5)=5$
$G(6)=8$
$G(7)=9$
$G(8)=13$
$G(9)=19$
$G(10)=19$
$G(11)=28$
$G(12)=35$
$G(13)=42$
$G(14)=50$
$G(15)=69$
$G(16)=95$
$G(17)=95$
$G(18)=131$
$G(19)=143$
$G(20)=194$
$G(21)=231$
$G(22)=265$
$G(23)=325$
$G(24)=431$
$G(25)=571$
$G(1000)=35900447427425971749758269477304230$
$G(2000)=682714394418480977725144681014302992073361435492835908$
...
$G(10^4)\approx 9.33\cdot 10^{146}$
After $n=10^4$ i can't calculate $G$ because recursion becames too deep.
We have to find numbers like $G(10^7) \mod 1000000007$
So function should be simplified somehow.

REPLY [0 votes]: There is a random walk in here.  Define a Markov chain like this.  Take $X_0 = x$, the starting point.  Assume $x > 0$.  Given $X_n$, flip a fair coin, and define $X_{n+1}$ to be either $X_n-1$ or $X_n-a$ (each possibility with probability $1/2$.)  This defines a Markov chain $(X_n)_{n \ge 0}$ in the real line.  For each step, the value decreases either by $1$ or by $a$.  
Define a "stopping time" $N$ by
$$
N = \inf\{n : X_n \le a\}
$$
the first time the walk goes below $a$.  This is how long it takes to go below $a$ when we start at $x$.  Let's say our "payoff" is $2^N$ if it takes $N$ steps.  
Then the expected value of the payoff
$$
f(x) = \mathbb E\left[2^N\right]
$$
satisfies
$$
f(x) = f(x-1)+f(x-a),\qquad x > a
$$
Also, if $x \le a$ then $N=0$, so $2^N=1$, and thus
$$
f(x) = 1,\qquad 0<x\le a.
$$  
Warning
The payoff is $2^N$, but that does not mean the expected payoff $f(x)$ is
$$
2^{\mathbb E [N]}
$$
Freshmen (and some physicists) may think every function is linear, but you should know that $2^n$ isn't linear.
{"set_name": "stack_exchange", "score": 1, "question_id": 1295323}