Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 3 down vote accepted

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

share|cite|improve this answer
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$.

share|cite|improve this answer

As Gortaur suggests, some additional restriction is necessary:





share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.