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