4
$\begingroup$

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.

  • 0
    Yeah, we can safely add this assumption. I have modified my question accordingly.2011-10-15

3 Answers 3

3

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$

  • 0
    @Topology: to notify dfeuer of a comment, put `@dfeuer` into the comment.2011-10-16
4

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

3

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

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

  • 1
    $x_n$ is only dependent on $f_m$ and $a$ in so far as $-1\le x_n\le1-f_m-a$. $x_n$ can be any value in that range. In any case, all we need to verify is the inequality $f_me^a(1+x_n)\le f_m+a+x_n$. Since both sides are linear in $x_n$, if we verify the inequality at both ends ($-1$ and $1-f_m-a$), it is verified everywhere in between.2011-10-18