# Question about a recursively defined function

Problem. Let $(f_n)_{n=1}^\infty$ be a sequence of functions $f_n\colon [-1,\infty)^n\to\mathbb{R}$ that are recursively defined in the following way:

$$f_1(x_1)=1+x_1,$$

$$f_n(x_1,\ldots,x_n) = \begin{cases} (1+x_n)f_{n-1}(x_1,\ldots,x_{n-1}) & \text{if } f_{n-1}(x_1,\ldots,x_{n-1}) \le 1, \\ x_n + f_{n-1}(x_1,\ldots,x_{n-1}) & \text{otherwise}. \end{cases}$$

Let $(g_n)_{n=1}^\infty$ be a sequence of functions $g_n\colon [-1,\infty)^n\to\mathbb{R}$ that are defined in the following way:

$$g_n(x_1,\ldots,x_n) = \prod_{k=1}^n (1+x_k).$$

Show, for any $n\ge1$ and any $x_1,\ldots,x_n\in[-1,\infty)$, that if $f_n(x_1,\ldots,x_n) <1$, it also holds that $g_n(x_1,\ldots,x_n) \le1$.

Observations. I have tried doing this with induction, but that doesn’t seem to work. It appears that I need more intricate knowledge of the relationship between $f_n$ and $g_n$ in order to solve the problem. Clearly, both are multivariate polynomials. It also seems like all the terms in $f_n$ are also contained in $g_n$, but I don’t know how that could help.

Real-life motivation. Note that the quantity $g_n(x_1,\ldots,x_n)$ is nothing but 1 dollar that has been invested in $n$ different ventures with percentage returns (positive or negative) of $x_1,\ldots,x_n$, where the profits from each venture have been reinvested in the next venture. The quantity $f_n(x_1,\ldots,x_n)$ is similar, except that profits are not reinvested. The objective is to show that if investing in ventures without reinvesting profits results in a loss, then reinvesting the profits couldn’t possibly have resulted in a profit.

-
You might want to add the assumption that $x_n\ge-1$ so that an investor doesn't lose more than they invest. – robjohn Oct 13 '11 at 23:09
Yeah, we can safely add this assumption. I have modified my question accordingly. – Topology Oct 15 '11 at 23:28

So, you have $$f_{i+1} = f_{i}+\min\{f_i,1\}x_{i+1}$$ and $$g_{i+1} = g_i+g_ix_{i+1}$$ with $f_0=g_0=1$. We assume from now that $x_i\geq 0$.

The idea is to consider separately intervals for positive or negative rates $x_i$ because on each such interval the dynamics of $f_i$ is simple. We put $$0=\tau_0<\sigma_1<\tau_1<\sigma_2<\tau_2<...$$ where for $k\in \mathbb N$ we define $\sigma_{k} = \inf\{i>\tau_{k-1}:f_i<1\}$ and $\tau_k = \inf\{i>\sigma_{k}:f_i\geq 1\}$. It means that $\sigma_1$ will be the first time $f$ will go below $1$ after $\tau_0=0$, $\tau_1$ - the first time $f$ will go above $1$ after $\sigma_1$; $\sigma_2$ is the first time $f$ goes below $1$ after $\tau_1$ etc.

Let us formulate the fact we use, it is proved below. For all $k \geq 0$ it holds that $$\begin{cases} \text{if }g_{\tau_k}\leq f_{\tau_k}&\text{ then }g_{\sigma_{k+1}}\leq f_{\sigma_{k+1}},\quad(*) \\ \text{if }g_{\sigma_{k+1}}\leq f_{\sigma_{k+1}}&\text{ then }g_{\tau_{k+1}}\leq f_{\tau_{k+1}}.\quad (**) \end{cases}$$

Suppose, the statement $(*),(**)$ is true. Since $g_{\tau_0} =g_0\leq f_0=f_{\tau_0}$, we have based on the statement above: $g_{\tau_k}\leq f_{\tau_k}$ and $g_{\sigma_{k+1}}\leq f_{\sigma_{k+1}}$ for all $k\geq 0$ $(***)$.

Let's show that it implies your statement: for all $i\geq 0$ it holds that $f_i<1\Rightarrow g_i\leq 1$.

1. If $\tau_k \leq i<\sigma_{k+1}$ for some $k\geq 0$ (the interval without reinvestment) then $f_i\geq 1$ and your statement is true.

2. If $\sigma_k \leq i<\tau_k$ for some $k\geq 1$ (the interval with reinvestment) then we have: $g_{\sigma_k}\leq f_{\sigma_k}<1$ by $(***)$. Moreover, the dynamics of $g$ and $f$ is the same on this interval, so $$\frac{g_i}{f_i} = \frac{g_{\sigma_k}}{f_{\sigma_k}}$$ on this interval and hence $g_i\leq f_i<1$.

We had consider all possible cases for $n$ and proved even stronger statement: if $f_i<1$ then $g_i\leq f_i$. We only need to prove $(*)$ and $(**)$ now.

We first prove $(*)$. Consider arbitrary $k\geq 0$ and for the shorthand let us denote $\tau_k = m$, $\sigma_{k+1}=n>m$ and we suppose as in $(*)$ that $g_m\leq f_m$.

1. if $n = m+1$ then $f_m\geq 1$ but $f_{m+1} = f_m+x_{m+1}<1$ so $-1<x_{m+1}<0$. We have: $$g_{m+1} = g_{m}(1+x_{m+1})\leq f_m(1+x_{m+1}) = f_m + f_mx_{m+1}\leq f_{m+1}$$ since $f_m\geq 1$ and $-1<x_{m+1}<0$.

2. suppose now that $n>m+1$ and denote $j = n-m-1>0$. So, $f_{m+i}\geq 1$ for all $0\leq i\leq j$ but $f_{m+j+1} = f_{n} <1$. Recall that $$f_{m+j} = f_m+\sum\limits_{i=1}^j x_{m+i}=: f_m+a.$$ On the other hand, $$g_{m+j} = g_m\prod\limits_{i=1}^j(1+x_{m+i})\leq g_m \exp\left\{\sum\limits_{i=1}^j x_{m+i}\right\} = g_m\mathrm e^{a}.$$ As a result we have: $$g_n = g_{m+j+1} = g_{m+j}(1+x_n)\leq g_m\mathrm e^a(1+x_n)\leq f_m\mathrm e^a(1+x_n)\leq f_m+a+x_n = f_n$$ Here we used conditions $f_m\geq 1,a\geq 0,-1<x_n<-f_m-a$ for the last inequality. So we considered all possible cases and proved $(*)$.

The proof of $(**)$ is much easier. If $g_{\sigma_{k+1}}\leq f_{\sigma_{k+1}}$ then unless $i<\tau_{k+1}$ you will always reinvest in both cases and $f,g$ will differ only by the same multiplier. That's why $g_{\tau_{k+1}}\leq f_{\tau_{k+1}}$.

-
You claim in several places that $x_k>-1$. It has been suggested in a couple of comments, but it should probably be mentioned in the proof.  In the proof of $(*)$, section 2., it is recalled that $x_{m+i}>0$ for all $1\le i\le j$. This is not necessarily so. We only know that $f_m\ge1$ and $f_{n-1}\ge1$ so we don't even know that $a=f_{n-1}-f_m>0$.  The whole part about arithmetic and geometric averages can be replaced with the fact that $\displaystyle\prod_{i=1}^j(1+x_{m+i})\le e^{\sum_{i=1}^jx_{m+i}}$. – robjohn Oct 14 '11 at 16:52
The conditions used include $f_m\ge1$, $a\ge0$ (which we don't know), and $-1<x_n<-f_m-a$. However, with these conditions, $f_m+a>1$ so the range $-1<x_n<-f_m-a$ is empty.  We do know that $f_m+a=f_{n-1}\ge1$ and $f_m+a+x_n=f_n<1$. So the range you may have intended above might be $-1<x_n<1-f_m-a$ – robjohn Oct 14 '11 at 16:53
Ah, when $x_n=-1$ the left side is $0$ and the right side is $f_n\ge0$. When $x_n=1-f_m-a$, the right side is $1$ and the left side is $f_me^a(2-f_m-a)\le e^a(1-a/2)^2\le1$ since $(1-a/2)\le e^{-a/2}$. – robjohn Oct 14 '11 at 22:43
I made a mistake in my last comment, when $x_n=-1$, the right side is $f_{n-1}-1\ge0$. Things are still okay, though. :-) – robjohn Oct 15 '11 at 15:17
Having shown the last inequality, all of my other comments above are easily correctable, so your answer will work. (+1) – robjohn Oct 15 '11 at 15:22

Define $\varphi(x)$ by $$\varphi(x)=\left\{\begin{array}{}x&\text{if }x\le1\\\exp(x-1)&\text{if }x>1\end{array}\right.\tag{1}$$ Note that $\varphi$ is monotonic increasing and $x\le\varphi(x)$ for all $x$.

Claim: $$(1+x)\varphi(y)\le\left\{\begin{array}{}\varphi((1+x)y)&\text{if }y\le1\\\varphi(x+y)&\text{if }y>1\end{array}\right.\tag{2}$$ Proof:

If $y\le1$, then $(1+x)\varphi(y)=(1+x)y\le\varphi((1+x)y)$.

If $y>1$ and $x+y>1$, then $(1+x)\varphi(y)\le\exp(x)\varphi(y)=\varphi(x+y)$.

If $y>1$ and $x+y\le1$, then $(1+x)\varphi(y)-\varphi(x+y)=(1+x)\exp(y-1)-(x+y)$.

As a function of $x$, $(1+x)\exp(y-1)-(x+y)$ is linear with a slope of $\exp(y-1)-1>0$. Thus, it reaches its maximum at $x=1-y$, but then \begin{align} (1+x)\exp(y-1)-(x+y) &\le\exp(x)\exp(y-1)-(x+y)\\ &=\exp(x+y-1)-(x+y)\\ &=0 \end{align} Therefore, $(1+x)\varphi(y)\le\varphi(x+y)$. $$\Box$$ So that no one loses more than they invest, I will assume $x_k\ge-1$.

Note that $g_0=\varphi(f_0)=1$. Suppose that $g_{n-1}\le\varphi(f_{n-1})$, then

if $f_{n-1}\le1$, then $g_n=(1+x_n)g_{n-1}\le(1+x_n)\varphi(f_{n-1})\le\varphi((1+x_n)f_{n-1})=\varphi(f_n)$.

if $f_{n-1}>1$, then $g_n=(1+x_n)g_{n-1}\le(1+x_n)\varphi(f_{n-1})\le\varphi(x_n+f_{n-1})=\varphi(f_n)$.

Thus, $g_n\le\varphi(f_n)$.

Conclusion: Perhaps I should add that this says that when $f_n\le1$ we have $g_n\le f_n$.

-

As Gortaur suggests, some additional restriction is necessary:

$f_1(3/2)=1+3/2=5/2$

$f_2(3/2,-2)=-2+5/2=1/2$

$f_3(3/2,-2,-2)=(1+(-2))(1/2)=-1/2<1$

$g_3(3/2,-2,-2)=(3/2+1)(-2+1)(-2+1)=5/2>1$

-
I would think that $x_n\ge-1$ would be a reasonable assumption since I don't think in many schemes does one lose more than they invest. – robjohn Oct 13 '11 at 23:08
Thanks dfeuer, you're right. The “$x_i\ge-1$” assumption has been added to the original question now. – Topology Oct 15 '11 at 23:29
@Topology: to notify dfeuer of a comment, put @dfeuer into the comment. – robjohn Oct 16 '11 at 7:43