An inequality on an arbitrary function

Question

I'm trying to find the complexity of a program and reduced the question to the following one:

Let $g$ be a function from natural numbers (including $0$) to natural numbers. Assume that for every $n \geq 1 $,

$$\sum_{k=0}^{2n} g(k) \leq a\cdot g(2n-1)$$ and $$\sum_{k=0}^{2n-1} g(k) \leq a\cdot g(2n-2)$$ and $0 < g(k) < g(k+1)$, $0 < a$ holds. It is easy to see that $a > 2$.

We want to minimize $a$, which is a real number.

For example, when $g(n) = 2^n$ and $a = 4$, inequality holds. Is there another function, $g$, such that $a < 4$?

Answer 1

Answer: No, there isn't.

Equivalent condition: $\forall n\ge 0, 0\lt g(n)\lt g(n+1)\le (a-1)\cdot g(n)-\sum_{k=0}^{n-1}g(k)$

Proof: Suppose there is a number $a\lt 4$ and a function $g(n)$ that satisfy the condition.

Assume there is some real number $x\lt a$ and an index $n\ge 0$ such that $$(a-1-x)\cdot g(n)\le \sum_{k=0}^{n-1}g(k)$$ Then, we find $g(n)\lt g(n+1)\le x\cdot g(n)$ using the reformulation above. From here, we also find that $x\gt 1$; so $x$ is positive and $1-\frac 1x\lt 1$. Then, we can write $\frac 1x\cdot g(n+1)\lt g(n)$. Because $a-x$ is also positive, we find that $\frac{a-x}x\cdot g(n+1)\le (a-x)\cdot g(n)$. $\frac{a-x}x$ can also be written as $a-1-a\left(1-\frac 1x\right)$. Here, $a(1-\frac 1x)\lt a$. In our assumption about $x$ and $n$, if we add $g(n)$ to both sides, we get $$\left(a-1-a\left(1-\frac 1x\right)\right)\cdot g(n+1)\le (a-x)\cdot g(n)\le\sum_{k=0}^ng(k)$$ so $a\left(1-\frac 1x\right)$ and $n+1$ satisfy the same condition they do.

Define a sequence $b(n)$ by $$\forall n\ge 1, b(n+1)=a\cdot (b(n)-b(n-1))$$ with $b(0)=1$ and $b(1)=a-1$. I claim that for all $n\ge 0$ the following are true: $$b(n)\gt 0, \frac{b(n+1)}{b(n)}\lt a, \left(a-1-\frac{b(n+1)}{b(n)}\right)\cdot g(n)\le\sum_{k=0}^{n-1}g(k)$$ Let me prove this by induction. For $n=0$, this becomes $1\gt 0, \frac{a-1}1\lt a, 0\cdot g(0)\le\sum_{k=0}^{-1}g(k)$ which is true. Now, assume it is true for some $n\ge 0$. Then, $\frac{b(n+1)}{b(n)}$ and $n$ satisfy the condition in the previous paragraph; so $a\left(1-\frac 1{b(n+1)/b(n)}\right)=\frac{b(n+2)}{b(n+1)}$ and $n+1$ satisfy it too. Also, $\frac{b(n+1)}{b(n)}$'s positivity means that $b(n+1)$ is positive too and this finishes the inductive step. The eigenvalues of the recurrence relation are $(a\pm\sqrt{a^2-4a})/2$. $b(1)$'s positivity means that $a\gt 1$, so the eigenvalues are complex. This means that $b(n)$'s closed form $$\frac{2{\sqrt a}^n}{\sqrt{4a-a^2}}\cdot\sin\left((n+2)\arctan\left(\sqrt{4/a-1}\right)\right)$$ is sinusoidal and will alternate signs. This contradicts our previous proof (based on the existence of $g$) that it would always stay positive.

Answer 2

I check the OP's example and tried a number of test functions, and couldn't find a function with $a < 4$.

Here's what I did:

If $g(n) = 2^n$, $\sum_{k=0}^{2n} g(k) =2^{2n+1}-1 =4\ 2^{2n-1}-1 <4\ 2^{2n-1} $.

So that's OK.

Let's try $g(n) = c^n$.

$\sum_{k=0}^{2n} g(k) =\sum_{k=0}^{2n} c^n =\frac{c^{2n+1}-1}{c-1} $ so we want $\frac{c^{2n+1}-1}{c-1} < ac^{2n-1} $ or $c^{2n+1}-1 < a(c-1)c^{2n-1} =ac^{2n}-ac^{2n-1} $ or $c <a-a/c+1/c^{2n} $ and this is true if $c \le a-a/c =a(1-1/c) =a\frac{c-1}{c} $ or $\frac{c^2}{c-1} \le a $.

Since the minimum value of $\frac{c^2}{c-1} $ is $4$ at $c=2$, $4$ is the best we can do for $g(n) = c^n$.

If $g(n) = n^c$, $\sum_{k=0}^{2n} g(k) =\sum_{k=0}^{2n} k^c =\frac{(2n)^{c+1}+O((2n)^c}{c+1} $ so we want $\frac{(2n)^{c+1}+O((2n)^c)}{c+1} < a(2n-1)^c $ or

$\begin{array}\\ (2n)^{c+1}+O((2n)^c) &< (c+1)a(2n-1)^c\\ \text{or, dividing by } (2n)^c\\ 2n+O(1) &< (c+1)a(1-1/(2n))^c\\ &\approx (c+1)a(1-c/(2n)) \qquad\text{for large } n \\ \end{array} $

and this will be false for any $a > 1$ for large enough $n$.

Let's try something that grows faster.

Suppose $g(n) = e^{n^2}$. $\sum_{k=0}^{2n} e^{k^2} > e^{(2n)^2} $ so we want $e^{(2n)^2} < ae^{(2n-1)^2} = ae^{(2n)^2-4n+1} $ or $e^{4n-1} < a$ which is false.

Answer 3

This is not intended to be a complete answer, it only show that if an exponential function is chosen, then the only base for which the inequality holds is $2$ and that $a$ must be 4.

If $g(x)$ is an exponential function of the form $b^x$, then $b$ must be two and $a$ must be 4 to make the inequality in OP true. $$\sum_{k=0}^{2n} b^k \leq ab^{2n-1} \Longrightarrow$$ $$\sum_{k=0}^{2n-2} b^k \leq ab^{2n-1} - b^{2n-1} - b\cdot b^{2n-1} $$ Using the identity $\sum_{k=0}^{n-1}ar^k =a\frac{1-r^n}{1-r}$ $$\frac{1-b^{2n-1}}{1-b} \leq (a - 1 -b) b^{2n-1}$$ Multiplying by negative quantity $1-b$ gives: $$1-b^{2n-1} \geq (a - 1 -b)(1-b) b^{2n-1} \Longrightarrow$$ $$1-b^{2n-1} \geq (a - 1 -ab+b^2) b^{2n-1} \Longrightarrow$$ $$1 \geq (a - 1 -ab+b^2) b^{2n-1} + b^{2n-1} \Longrightarrow$$ $$1 \geq (a-ab+b^2) b^{2n-1} \tag{1}$$ Because $b>1$ then $b^{2n-1}$ can be arbitrarily large. Therefore $a-ab+b^2$ must be zero to make (1) true. This expression has zeroes only when $a \leq 0$ or $a \geq 4$. When $a=4$, $b$ must be 2 to make expression zero.

Answer 4

Warning: the answer is not perfectly checked, I'll hope to do it later.

I can show that $a>3$ as follows.

For the sake of simplicity I put $h(n)=g(n)/g(0)$ and $c=1/(a-2)$. Then $h(0)=1$, the sequence $\{h(n)\}$ increases and

$$h(0)+\dots+ h(n+1)\le ah(n)$$

for each $n\ge 0$.

In particular,

$h(0)+h(1)\le ah(0)$, so $h(1)\le a-1$.

On the other hand,

$h(0)+h(1)+h(1)<h(0)+h(1)+h(2)\le ah(1)$, so

$1<(a-2)h(1)$, and $c=1/(a-2)<h(1)$.

Next,

$h(0)+h(1)+h(2)\le ah(1)$, so

$h(2)\le (a-1)h(1)-1\le (a-1)^2-1=a^2-2a$.

On the other hand,

$h(0)+h(1)+h(2)+h(2)<h(0)+h(1)+h(2)+h(3)\le ah(2)$, so

$c<h(1)<(a-2)h(2)-1$

$c^2+c=(1+c)/(a-2)<h(2)$.

At last,

$h(0)+h(1)+h(2)+h(3)\le ah(2)$, so

$h(3)\le (a-1)h(2)-h(1)-h(0)<(a-1)(a^2-2a)-c-1$.

On the other hand,

$h(0)+h(1)+h(2)+h(3)+h(3)<h(0)+h(1)+h(2)+h(3)+h(4)\le ah(3)$, so

$1+c+c^2+c<h(0)+h(1)+h(2)<(a-2)h(3)<(a-2)((a-1)(a^2-2a)-c-1)$

$c+2c^2+c^3<(a-1)(a^2-2a)-c-1$

$1+2c+2c^2+c^3<(a-1)a(a-2)=(1/c+1)(1/c+2)/c$

$c^3+2c^4+2c^5+c^6<(1+c)(1+2c)$

$(c+1)^2(c-1)(c^3+c^2+2c+1)<0$

$1/(a-2)=c<1$

$a>3$.

PS. The next ideas look promising, but now I’m too tired to check them. It seems that inductively extending the above arguments for $c<1$ and any $n$ we can show that

$$c^n<h(n)/(a-1)^{n-1}<(1-c-c^2+c^{n+1})/(c-c^2),$$

which implies $c^2+c-1\le 0$, $c\le (\sqrt{5}-1)/2$ or $a\ge (5+\sqrt{5})/2\simeq 3.618.$