1

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.

norman
  • 11
  • I don't know the answer. For a start I would advice you to calculate the function in some interesting points. E.g. $f(a) = f(a-1)+f(a-a) = 1 + f(0) = 1+1 = 2$, because $a-1<a$ and $0<a$ for arbitrary $a>1$. Similarly $f(a+1) = \cdots = 3$. – quapka May 23 '15 at 12:51
  • Also if I haven't done any mistake, and assuming the pattern goes on (that would require proof by induction), then it holds, that $n \in \mathbb{N}: f(na) = f(na-1) + f((n-1)a-1)+\cdots +f(3a-1)+f(2a-1)+2$. – quapka May 23 '15 at 13:00
  • Is $a$ some specific rational number? – Jack D'Aurizio May 23 '15 at 13:13
  • Do you know something about random walks? – GEdgar May 23 '15 at 13:25
  • See if you can calculate the first few values, and tell us what you get. – Empy2 May 23 '15 at 13:53
  • @GEdgar, i know a bit, you think it could help here? – norman May 23 '15 at 14:52
  • Build up the values from $f(\sqrt{N})$ to $f(N)$. There is a new value for every $p+q\sqrt{N}$, so around $N\sqrt{N}$ in all, but if you are careful you only need to keep $N$ of them in memory at any one time. – Empy2 May 24 '15 at 04:55
  • There is explicit formula for it. – norman May 26 '15 at 10:20
  • This is the current Project Euler question. – Empy2 May 26 '15 at 16:43
  • yes, i already solved it, binary tree and as a result formula for $g(a,x)$ contains binomial coefficients. – norman May 27 '15 at 15:57

1 Answers1

0

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.

GEdgar
  • 111,679
  • thanks, i dont really familiar with markov chain, as i know we have to define transition matrix and then do fast matrix exponentiation to get expected values of steps to reach desired position. so whats the dimention of the transition matrix there? is it $\sqrt n$ x $ \sqrt n$? – norman May 24 '15 at 10:06