sequence positive

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

sequence positive

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: ISL 2006, A2, VAIMO 2007, P4, Poland 2007

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

89 posts

#1 h Apr 22, 2007, 2:36 AM • 12 Y

Y by itslumi, mathematicsy, jhu08, HWenslawski, megarnie, Adventure10, Mango247, cliid, BorivojeGuzic123, and 3 other users

The sequence of real numbers $a_0,a_1,a_2,\ldots$ is defined recursively by $a_0=-1,\qquad\sum_{k=0}^n\dfrac{a_{n-k}}{k+1}=0\quad\text{for}\quad n\geq 1.$ Show that $a_{n} > 0$ for all $n\geq 1$ .

Proposed by Mariusz Skalba, Poland

This post has been edited 1 time. Last edited by djmathman, Jun 27, 2015, 12:05 AM
Reason: changed problem statement to match english version of ISL2006

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

89 posts

Goblin

#2 h Apr 22, 2007, 11:48 AM • 13 Y

Y by anantmudgal09, Supercali, mijail, Adventure10, jhu08, veirab, Mango247, Kingsbane2139, and 5 other users

We can use induction. For $n=1$ this is trivial. Now, if it's true for $m\leq n$ , from $(n+1)a_{n}+\frac{n+1}{2}a_{n-1}+\ldots+a_{0}=0$ and $(n+2)a_{n+1}+\frac{n+2}{2}a_{n}+\ldots+a_{0}=0$ , we get $(n+2)a_{n+1}=\sum_{i=0}^{n}a_{i}\left(\frac{n+1}{n+1-i}-\frac{n+2}{n+2-i}\right)=\sum_{i=0}^{n}a_{i}\frac{i}{(n+1-i)(n+2-i)}$ which is positive.
I really think that it's not OK that you posted this problem.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6555 posts

#3 h Jun 12, 2007, 11:42 PM • 7 Y

Y by jhu08, Adventure10, Mango247, and 4 other users

I rather think it is not OK that this problem was used in the Polish MO...

Darij

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

232 posts

edriv

#4 h Jun 13, 2007, 9:13 PM • 5 Y

Y by Aryan-23, Adventure10, jhu08, Mango247, and 1 other user

Goblin wrote:

I really think that it's not OK that you posted this problem.

And I think it's not ok you know that this problem is not ok

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

514 posts

#5 h Jan 3, 2009, 3:11 PM • 5 Y

Y by Samusasuke, jhu08, Adventure10, Mango247, and 1 other user

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

30 posts

#6 h Jun 26, 2012, 8:08 PM • 5 Y

Y by expotential, jhu08, Adventure10, Mango247, and 1 other user

malinger wrote:

Let $a_{0},a_{1},a_{2},\ldots$ be a sequence of reals such that $a_{0} = - 1$ and

$a_{n} + \frac {a_{n - 1}}{2} + \frac {a_{n - 2}}{3} + \ldots + \frac {a_{1}}{n} + \frac {a_{0}}{n + 1} = 0$ for all $n\geq 1$ .

Show that $a_{n} > 0$ for all $n\geq 1$ .

Proposed by Mariusz Skalba, Poland

Solution that uses Cauchy-Schwarz inequality.

We can write the following formula for $n$ :

$a_n=-\frac{a_{n-1}}{2}-...-\frac{a_1}{n}-\frac{a_0}{n+1}$ , $(1)$ .

and for $n-1$ :

$0=\frac{a_{n-1}}{1}+\frac{a_{n-2}}{2}+...+\frac{a_0}{n}$ . $(2)$ .

Adding up equations $(1)$ and $(2)$ we get:

$a_n=a_{n-1}(1-\frac{1}{2})+a_{n-2}(\frac{1}{2}-\frac{1}{3})+...+a_0(\frac{1}{n}-\frac{1}{n+1})$ ,

or:

$a_n=\frac{a_{n-1}}{1 \cdot 2}+\frac{a_{n-2}}{2 \cdot 3}+...+\frac{a_0}{n \cdot (n+1)}$ for all $n \geq 2$ .

Let's prove the assertation by induction on $n$ . The base for $n=1$ is obvious: $a_1=-\frac{a_0}{2}=\frac{1}{2}>0$ . Let's suppose that the assertation is true for all integers from $1$ till $n-1$ : $a_i>0$ $\forall i \in \{1,2,...,n-1\}$ . By Cauchy-Schwarz inequality:

$(\frac{a_{n-1}}{1 \cdot 2}+\frac{a_{n-2}}{2 \cdot 3}+...+\frac{a_1}{(n-1) \cdot n})(\frac{2a_{n-1}}{1}+\frac{3a_{n-2}}{2}+...+\frac{na_1}{n-1}) \geq (\frac{a_{n-1}}{1}+$
$+\frac{a_{n-2}}{2}+...+\frac{a_1}{n-1})^2$ .

Using equation $(2)$ :

$\frac{a_{n-1}}{1 \cdot 2}+\frac{a_{n-2}}{2 \cdot 3}+...+\frac{a_1}{(n-1) \cdot n} \geq \frac{a_0^2}{n^2(\frac{2a_{n-1}}{1}+\frac{3a_{n-2}}{2}+...+\frac{na_1}{n-1})}$ .

But:

$2a_{n-1}+\frac{3}{2}a_{n-2}+...+\frac{n}{n-1}a_1=(a_{n-1}+\frac{a_{n-2}}{2}+...+$
$+\frac{a_1}{n-1})+(a_{n-1}+\frac{a_{n-2}}{2}+...+\frac{a_1}{n-1})+(\frac{a_{n-2}}{2}+\frac{a_{n-3}}{3}+...+\frac{a_1}{n-1})+(\frac{a_{n-3}}{3}+$
$+...+\frac{a_1}{n-1})+...+\frac{a_1}{n-1} \leq n \cdot \frac{-a_0}{n}=-a_0$

by the equation $(2)$ and since numbers $a_1, a_2, ..., a_{n-1}>0$ . Thus:

$\frac{a_{n-1}}{1 \cdot 2}+\frac{a_{n-2}}{2 \cdot 3}+...+\frac{a_1}{(n-1) \cdot n} \geq \frac{a_0^2}{n^2 \cdot (-a_0)}=\frac{-a_0}{n^2}$ .

So:

$a_n=(\frac{a_{n-1}}{1 \cdot 2}+\frac{a_{n-2}}{2 \cdot 3}+...+\frac{a_1}{(n-1) \cdot n})+\frac{a_0}{n(n+1)} \geq \frac{-a_0}{n \cdot n}+\frac{a_0}{n(n+1)}=\frac{1}{n \cdot n}-$
$-\frac{1}{n \cdot (n+1)}=\frac{1}{n^2(n+1)}>0$ ,

as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

56 posts

andywu

#7 h May 9, 2015, 11:28 AM • 3 Y

Y by jhu08, Adventure10, Mango247

n=1 is trivial
let if n<k or n=k ,we have $a_{n}>0$
n=k+1:
we know that
$a_{k}+\frac{a_{k-1}}{2}+...+\frac{a_1}{k}+\frac{a_0}{k+1}=0$
$\frac{a_{k}}{2}+...+\frac{a_1}{k+1}+\frac{a_0}{k+2} < = (a_{k}+\frac{a_{k-1}}{2}+...+\frac{a_1}{k})*\frac{k}{k+1}+\frac{a_0}{k+2} = -\frac{a_0}{k+1}*\frac{k}{k+1}+\frac{a_0}{k+2} =(\frac{1}{k+2}-\frac{k}{(k+1)^2})a_0 =\frac{1}{(k+2)(k+1)^2}a_0 <0$
so that a_(k+1)>0

by MIT , we done

This post has been edited 3 times. Last edited by andywu, May 9, 2015, 11:33 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1059 posts

#8 h Mar 2, 2016, 10:07 AM • 5 Y

Y by Tintarn, 62861, anantmudgal09, jhu08, Adventure10

ISL 2006 wrote:

Students familiar with the technique of generating functions will immediately recognise $\sum a_nx^n$ as the power series expansion of $x/ \log(1-x)$ (with value $-1$ at $0$ ). But this can be a trap; attempts along these lines lead to unpleasant differential equations and integrals hard to handle. Using only tools from real analysis (e.g. computing the coefficients from the derivatives) seems very difficult.

It isn't that difficult! There exists a solution with only real analysis, and a pretty tasteful integral formula for the coefficients.

Problem

Formula

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

986 posts

Kezer

#9 h Aug 24, 2016, 12:14 PM • 5 Y

Y by jhu08, Adventure10, Mango247, BorivojeGuzic123, Ulapu_Kanama

Uhm, kind of felt a little bit contrived.

We'll induct on $n$ . As $a_1+\tfrac{a_0}{2} = 0 \iff a_1 = \tfrac12$ , the number $a_1$ is positive. Now assume $a_1,a_2,\dots,a_n >0$ . Note $0=\sum_{k=0}^n \frac{a_{n-k}}{k+1} = a_n + \frac{a_{n-1}}{2}+\frac{a_{n-2}}{3}+\dots+\frac{a_0}{n+1} \qquad \text{and} \qquad 0=\sum_{k=0}^{n+1} \frac{a_{n+1-k}}{k+1} = a_{n+1} + \frac{a_{n}}{2}+\frac{a_{n-1}}{3}+\dots+\frac{a_0}{n+2}$ Subtracting yields $0 = a_{n+1}-\frac{a_n}{2}-\frac{a_{n-1}}{6}-\frac{a_{n-2}}{12}-\dots-\frac{a_0}{(n+2)(n+1)} \iff a_{n+1} = \sum_{k=0}^{n} \frac{a_{n-k}}{(k+1)(k+2)}.$ But now note $\begin{align*} a_{n+1} = \sum_{k=0}^{n} \frac{a_{n-k}}{(k+1)(k+2)} &= \sum_{k=0}^{n-1}\frac{a_{n-k}}{(k+1)(k+2)} + \frac{a_0}{(n+2)(n+1)} \\ &\geq \sum_{k=0}^{n-1}\frac{a_{n-k}}{(n+1)(k+1)} + \frac{a_0}{(n+2)(n+1)} \\ &= \frac{1}{n+1} \left( \sum_{k=0}^{n-1}\frac{a_{n-k}}{k+1} + \frac{a_0}{n+2} \right) \\ &= \frac{1}{n+1} \left( -\frac{a_0}{n+1} + \frac{a_0}{n+2} \right) \\ &> 0 \end{align*}$ Done, yay! It really worked, wow, needed the write-up to confirm that.

This post has been edited 1 time. Last edited by Kezer, Aug 24, 2016, 12:25 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

HadjBrahim-Abderrahim

169 posts

HadjBrahim-Abderrahim

#10 h Feb 7, 2017, 6:32 PM • 2 Y

Y by jhu08, Adventure10

malinger wrote:

The sequence of real numbers $a_0,a_1,a_2,\ldots$ is defined recursively by $a_0=-1,\qquad\sum_{k=0}^n\dfrac{a_{n-k}}{k+1}=0\quad\text{for}\quad n\geq 1.$ Show that $a_{n} > 0$ for all $n\geq 1$ .

Proposed by Mariusz Skalba, Poland

Here is my solution, we prove the problem by induction on $n\ge 1.$ When $n=1$ we have, $0=a_1+\frac{a_0}{2},$ which means that $a_1=-\frac{a_0}{2}=\frac{1}{2}>0.$ Assume that the numbers $a_1,a_2,\ldots,a_n$ are greater then zero for some positive integer $n.$ Since $x_0=-1<0,$ we can see that we will have some problems when we keep it and try to prove that $a_{n+1}>0,$ so we try to remove it. Because, $\sum_{k=0}^{n+1} \frac{a_{n+1-k}}{k+1}=\sum_{k=0}^{n}\frac{n-k}{k+1}=0,$ we have $\begin{align*} a_{n+1}(n+2)&=(n+1)\left(a_n+\frac{a_{n-1}}{2}+\cdots+\frac{a_0}{n+1}\right)-(n+2)\left(\frac{a_n}{2}+\frac{a_{n-1}}{3}+\cdots+\frac{a_0}{n+2}\right)\\&=(n+1)\sum_{i=0}^{n-1}\frac{a_{n-i}}{i+1}+(n+2)\sum_{i=0}^{n-1}\frac{a_{n-i}}{i+2}\\&=\sum_{i=0}^{n-1}\frac{(n-i)a_{n-i}}{(i+1)(i+2)}>0,\end{align*}$ which means that $a_{n+1}>0.$ This ends the induction and solves the problem.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1576 posts

#11 h Apr 16, 2020, 3:08 AM • 1 Y

Y by jhu08

We will use induction. Note that the base case is trivial, so assume $a_{n-1},\ldots, a_1>0$ . We have that $\sum_{k=0}^{n-2}\frac{a_{n-1-k}}{k+1}=\frac{1}{n}$ , so $\sum_{k=0}^{n-2}\frac{n-1}{n}\cdot\frac{a_{n-1-k}}{k+1}=\frac{n-1}{n^2}\implies\sum_{k=1}^{n-1}\frac{a_{n-k}}{k+1}<\frac{n-1}{n^2}\implies a_n=-\sum_{k=1}^n\frac{a_{n-k}}{k+1}>\frac{1}{n+1}-\frac{n-1}{n^2}=\frac{1}{(n+1)n^2}>0$ as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6882 posts

#12 h Apr 19, 2020, 1:33 PM • 4 Y

Y by mathiscool12, v4913, jhu08, BorivojeGuzic123

Solution from Twitch Solves ISL:

In fact, it suffices to take the two consecutive equations $\begin{align*} 0 &= \frac{a_n}{1} + \frac{a_{n-1}}{2} + \frac{a_{n-2}}{3} + \dots + \frac{a_0}{n+1} \\ 0 &= \frac{a_{n+1}}{1} + \frac{a_n}{2} + \frac{a_{n-1}}{3} + \frac{a_{n-2}}{4} + \dots + \frac{a_0}{n+2} \end{align*}$ and subtract $\frac{n+1}{n+2}$ times the first equation from the second (eliminating the $a_0$ ) to obtain a new recursion $\begin{align*} a_{n+1} &= \left( \frac{n+1}{n+2} \cdot \frac11 - \frac12 \right) a_n + \left( \frac{n+1}{n+2} \cdot \frac12 - \frac13 \right) a_{n-1} \\ &\qquad+ \left( \frac{n+1}{n+12} \cdot \frac13 - \frac14 \right) a_{n-2} + \dots + \left( \frac{n+1}{n+2} \cdot \frac1n - \frac1{n+1} \right) a_1. \end{align*}$ This recursion has the property that all the coefficients in parentheses are positive. Since $a_1 = 1/2 > 0$ , this implies the result by induction.

This post has been edited 2 times. Last edited by v_Enhance, Jun 5, 2020, 8:15 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

52 posts

#13 h Apr 21, 2020, 8:02 PM • 1 Y

Y by jhu08

@above
Hi Evan,to eliminate $a_0$ we need to subtract $\frac{n+1}{n+2}$ of the 1st equation from the 2nd one.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6882 posts

#14 h Apr 22, 2020, 12:32 AM • 5 Y

Y by v4913, jhu08, Mango247, Mango247, Mango247

I really messed up all the indices, huh

Fixed, thanks for pointing it out.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1671 posts

pad

#15 h Apr 25, 2020, 8:02 AM • 1 Y

Y by jhu08

Induct on $n$ , the case $n=1$ trivial since $a_1=1/2$ . So we can assume $a_1,\ldots,a_{n-1}>0$ ; this makes all the inequalities easier to deal with. Note that
$\frac{a_1}{n-1} + \frac{a_2}{n-2} + \cdots + \frac{a_{n-1}}{1} = \frac{1}{n} \implies \frac{1}{n}a_1 + \frac{n-1}{n(n-2)}a_2 + \cdots + \frac{n-1}{n} a_{n-1} = \frac{n-1}{n^2}.$ That is,
$\sum_{k=1}^{n-1} \frac{n-1}{n(n-k)}a_k = \frac{n-1}{n^2}.$ In order to show $a_n>0$ , we want to show
$\frac{a_1}{n} + \frac{a_2}{n-1} + \cdots + \frac{a_{n-2}}{3} + \frac{a_{n-1}}{2} = \sum_{k=1}^{n-1} \frac{a_k}{n+1-k} < \frac{1}{n+1}.$ We see that $\tfrac{n-1}{n(n-k)} \ge \tfrac{1}{n+1-k} \iff (n-1)(n-k+1) \ge n(n-k) \iff k\ge1$ , which is always true. And it is easy to see that $\tfrac{1}{n+1} > \tfrac{n-1}{n^2}$ . Hence,
$\frac{1}{n+1} > \frac{n-1}{n^2} = \sum_{k=1}^{n-1} \frac{n(n-1)}{n(n-k)}a_k \ge \sum_{k=1}^{n-1} \frac{a_k}{n+1-k} .$ This completes the proof.

Remarks

This post has been edited 1 time. Last edited by pad, Apr 25, 2020, 8:05 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2726 posts

#16 h Jun 23, 2020, 5:00 AM • 1 Y

Y by jhu08

It suffices to show that $\tfrac{a_1}{n} + \tfrac{a_2}{n-1} + \ldots + \tfrac{a_{n-1}}{2}< \tfrac{1}{n+1}$ for all positive integer $n \geq 2$ . We strong induct on $n$ .

The base cases are clear; We can easily calculate $a_2 = \tfrac12$ and $a_2 = \tfrac{1}{12}$ . Note that $\tfrac14 < \tfrac13$ and $\tfrac{5}{24} < \tfrac14$ hence $n = 2$ and $n = 3$ hold as desired.

In the inductive step, we are allowed to assume that the result holds for all $n \leq k$ . Hence by the inductive hypothesis we may assume that the terms $a_0, a_1, \ldots , a_k$ are all positive and $\tfrac{a_1}{k} + \tfrac{a_2}{k-1} + \ldots + \tfrac{a_{k-1}}{2}< \tfrac{1}{k+1}$ . We are motivated to relate the LHS to something we can find. More specifically, we can actually derive from the problem recursion that $\frac{a_1}{k} + \frac{a_2}{k-1} + \ldots + \frac{a_{k}}{1} = \frac{1}{k+1}.$ Multiplying both sides by $\tfrac{k}{k+1}$ yields $\frac{a_1(k)}{(k)(k+1)} + \frac{a_2(k)}{(k-1)(k+1)} + \ldots + \frac{a_{k}(k)}{(1)(k+1)} = \frac{k}{(k+1)^2}.$ In fact, we can actually check that $\tfrac{1}{k+2 - i} \leq \tfrac{k}{(k+1-i)(k+1)} \implies k^2 + 2k \geq (k+1)^2 - i$ is always true hence by our inductive hypothesis, the expression we seek, $S$ , can be bounded: $S \leq \frac{k}{(k+1)^2} < \frac{1}{k+2}$ as desired. $\blacksquare$

Remark: Induction was intuitive. I also wrote everything in non-summation notation because maybe it would be more clear to see the pattern? Also note that our entire comparison of sequences is correct because all previous terms are positive by inductive hypothesis.

This post has been edited 1 time. Last edited by jj_ca888, Jun 23, 2020, 5:01 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1522 posts

#17 h Sep 5, 2021, 11:20 PM • 1 Y

Y by jhu08

Click to reveal hidden text

This post has been edited 1 time. Last edited by bever209, Sep 5, 2021, 11:24 PM
Reason: my brain ded

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

579 posts

#18 h Sep 16, 2021, 2:00 PM • 1 Y

Y by WolfusA

Note that
$(n+1) \left(\frac{a_0}{n+1} + \frac{a_1}{n} + \cdots + \frac{a_{n-1}}{2}+\frac{a_n}{1}\right)=0=n\left(\frac{a_0}{n} + \frac{a_1}{n-1}+\cdots + \frac{a_{n-1}}{1}\right)$ Thus,
$(n+1)a_n = \sum_{i=1}^{n-1} \left(\frac{n}{n-i}-\frac{n+1}{n-i+1}\right) a_{i}=\sum_{i=1}^{n-1} \left(\frac{i}{(n-i)(n-i+1)}\right) a_{i}$
Using this we claim by induction that for all $n\geq 1$ , we have $a_n>0.$ Clearly this is true for $a_1 = \frac12 >0$ . Then, by the previous equation the inductive step is clear, so we're done. $\blacksquare$ .

This post has been edited 4 times. Last edited by AwesomeYRY, Sep 16, 2021, 2:03 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1926 posts

#19 h Jun 30, 2022, 4:54 PM

Y by

We proceed by strong induction. $a_1=\frac12>0$ .
$0=\frac{n+1}{n+2}\sum_{k=0}^{n}\frac{a_{n-k}}{k+1}>\sum_{k=1}^{n+1}\frac{a_{n+1-k}}{k+1}=\sum_{k=0}^{n+1}\frac{a_{n+1-k}}{k+1}-a_{n+1}\rightarrow \boxed{a_{n+1}>0}.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7585 posts

#20 h Jul 31, 2022, 1:43 AM

Y by

A2?

We use strong induction; the base case $n=1$ is trivial. We have that
$\frac{a_n}{1}+\frac{a_{n-1}}{2}+\dots+\frac{a_1}{n}=\frac{1}{n+1}$ and since
$\frac{a_n}{2}+\frac{a_{n-1}}{3}+\dots+\frac{a_1}{n+1}<\frac{a_n}{1\cdot \tfrac{n+2}{n+1}}+\frac{a_{n-1}}{2\cdot \frac{n+2}{n+1}}+\dots+\frac{a_1}{n\cdot \tfrac{n+2}{n+1}}=\frac{1}{n+2}$ we get
$\frac{a_{n+1}}{1}=\frac{1}{n+2}-\left(\frac{a_n}{2}+\frac{a_{n-1}}{3}+\dots+\frac{a_1}{n+1}\right)>0$ so we are done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1742 posts

awesomeming327.

#21 h Aug 2, 2022, 6:40 PM

Y by

Let $P(n)=\sum_{k=0}^n\dfrac{a_{n-k}}{k+1}$ , then $0=nP(n-1)-(n+1)P(n).$ Thus, $0=-(n+1)a_{n}+\left(\frac{n+1}{2}-n\right)a{n-1}+\left(\frac{n+1}{3}-\frac{n}{2}\right)a{n-2}+\dots$ and $\frac{n+1}{k}-\frac{n}{k-1}$ here is always positive, unless $k=n+1$ where it's zero, so $(n+1)a_n>0$ implying result.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5005 posts

#22 h Aug 7, 2022, 2:03 AM

Y by

Induction on $n$ , with $n=1$ trivial. Now, suppose that for some $n-1$ , we have $a_{n-1},\ldots,a_1>0$ . The idea is to separate the sum
$\boxed{\frac{a_{n-1}}{1}+\frac{a_{n-2}}{2}+\cdots+\frac{a_1}{n-1}}+\boxed{\frac{a_0}{n}}$ into positive and negative parts as shown. Now, going from the above equation to
$\frac{a_{n-1}}{2}+\frac{a_{n-2}}{3}+\cdots+\frac{a_1}{n}+\frac{a_0}{n+1}:=S,$ we multiply the positive part of the equation by at most $\tfrac{n-1}{n}$ (by considering each term), while we multiply the negative part of the equation by $\tfrac{n}{n+1}>\tfrac{n-1}{n}$ , hence $S<0$ . Since $S+\tfrac{a_n}{1}=0$ , it follows that $a_n>0$ , finishing the induction. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

225 posts

#23 h Dec 21, 2022, 4:37 PM

Y by

We use induction, and the base case that $a_1=\frac12>0$ is easy to check. Now assume that it is true for $n=m-1$ . Then for $n=m$ we know that
$a_{m}+\frac{a_{m-1}}{2}+\frac{a_{m-2}}{3}+\ldots+\frac{a_0}{m+1}=0$ and also that
$a_{m-1}+\frac{a_{m-2}}{2}+\frac{a_{m-3}}{3}+\ldots+\frac{a_0}{m}=0$ Multiplying both equations by $m+1$ and $m$ respectively, and then subtracting the second from the first, we get
$a_m+\left(\frac{(m+1)a_{m-1}}{2}-ma_{m-1}\right)+\left(\frac{(m+1)a_{m-2}}{3}-\frac{ma_{m-2}}{2}\right)+\ldots+0=0$ Notice that $\frac{j+1}{i+1}-\frac{j}{i}<0$ as long as $j>i>0$ , which is always the case here for $m+1$ and the denominator of each fraction. As all the $a_i$ are greater than $0$ by the induction hypothesis, each term in paranthesis is less than $0$ , making $a_m>0$ , which finishes the proof.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8872 posts

#24 h Jan 7, 2023, 3:00 AM

Y by

We will proceed strong inductively. Consider the two equations
$\begin{align*} \frac{a_0}n + \frac{a_1}{n-1} + \frac{a_2}{n-2} + \cdots + a_n &= 0 \\ \frac{a_0}{n+1} + \frac{a_1}n + \frac{a_2}{n-1} +\cdots + \frac{a_n}2+a_{n+1} &=0. \end{align*}$ Subtracting $n$ times the first from $n+1$ times the second, $(n+1)a_{n+1} - a_n - \sum_{i=1}^n \frac{a_{n-i}}{i(i+1)} = 0.$ But all the terms subtracted are positive by the hypothesis, so this implies $a_{n+1} > 0$ as well.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

559 posts

#25 h Jan 10, 2023, 8:56 PM

Y by

Induct on $n>0.$ We trivially deduce that $a_1=\frac 12,$ providing the base case $n=1.$ Next, the inductive step follows from
$(n+2)a_{n+1}=\sum_{k=0}^n \left( \frac{n+1}{n-k+1}-\frac{n+2}{n-k+2} \right)a_k=\sum_{k=1}^n \frac{ka_k}{(n-k+1)(n-k+2)}>0\quad \blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1292 posts

#26 h Jul 31, 2023, 8:39 PM

Y by

Not sure why this was even in shortlist...
Base case is done with $a_1=1/2$ . Inductive step: We know $\frac{a_{n-1}}{1}+\cdots+\frac{a_1}{n-1}=-\frac{a_0}{n} \text{ (1)},$ and want to prove $\frac{a_{n-1}}{2}+\cdots+\frac{a_1}{n}<-\frac{a_0}{n+1} \text{ (2)}$ because it would follow that $a_n$ would need to be positive s.t. the LHS is added with a positive number to maintain equality. Indeed, note that each term of LHS of (1) is multiplied by at most (n-1)/n to get LHS (2), while RHS of (1) is multiplied by n/(n+1). Put rigorously, RHS(2)=RHS(1)n/(n+1) $>$ RHS(1)(n-1)/n=LHS(n-1)/n $>$ LHS(2), as desired. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1748 posts

OronSH

#27 h Jan 15, 2024, 3:38 PM

Y by

solved with grents

First $a_1=\frac12>0.$ Consider $n\sum_{k=0}^{n-1}\frac{a_{n-k-1}}{k+1}-(n+1)\sum_{k=0}^n \frac{a_{n-k}}{k+1}=0.$ This rearranges to $\sum_{k=1}^{n-1} a_k\left(\frac n{n-k}-\frac{n+1}{n+1-k}\right)=a_n(n+1)$ and we easily see that $\frac n{n-k}>\frac {n+1}{n+1-k}$ so we finish by induction.

bruh

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

370 posts

#28 h Mar 9, 2024, 4:59 AM

Y by

This problem is easier than A1 in my opinion...

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

37 posts

#29 h Jun 11, 2024, 8:13 PM • 1 Y

Y by OronSH

We use induction. Our base case is $n=1$ , for which we can easily calculate $a_1=\frac 12$ . Now for the inductive step, we assume that $a_i$ is positive for $1\leq i \leq n$ , and we will prove that $a_{n+1}>0$ must also hold.

By the definition of the sequence, we have the following two equalities:
$\begin{align*} 0&=\sum_{k=0}^n\dfrac{a_{n-k}}{k+1} \\ -a_{n+1}&=\sum_{k=0}^n\dfrac{a_{n-k}}{k+2} \end{align*}$
We multiply the first equation by $\frac{n+1}{n+2}$ to get
$\sum_{k=0}^n\dfrac{(n+1)a_{n-k}}{(k+1)(n+2)}=0.$
We will compare this sum term-by-term with the sum from our second equation. We notice that since $k\leq n$ , $\frac{k+1}{k+2}\leq\frac{n+1}{n+2}$ , and thus $\dfrac{a_{n-k}}{k+2} \leq \dfrac{(n+1)a_{n-k}}{(k+1)(n+2)}$ , with the terms being equal only when $k=n$ . This means that all of the positive terms of $\sum_{k=0}^n\dfrac{a_{n-k}}{k+2}$ are smaller than their respective terms in $\sum_{k=0}^n\dfrac{(n+1)a_{n-k}}{(k+1)(n+2)}$ , while the negative term is the same, which tells us that
$\sum_{k=0}^n\dfrac{a_{n-k}}{k+2}<\sum_{k=0}^n\dfrac{(n+1)a_{n-k}}{(k+1)(n+2)}=0$
Since $-a_{n+1}=\sum_{k=0}^n\dfrac{a_{n-k}}{k+2}$ and we have determined the right side sum is negative, $a_{n+1}$ must be positive, which completes the induction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

334 posts

#30 h Jul 27, 2024, 6:33 AM

Y by

We will use induction on $n$ . The base case is clear.
Claim: For any $k \le n$ ,
$\frac{1}{k-1} \cdot \frac{n}{n+1} > \frac{1}{k}$ Proof: Trivial by expanding. $\square$
Now assume $a_{\ell} > 0$ for all $\ell \le n-1$ , and we will prove $a_n > 0$ . From taking the sum to $n-1$ and $n$ we get:
$\sum_{i = 1}^{n-1} \frac{a_{n-i}}{i} = -\frac{a_0}{n}$ $\sum_{i = 0}^{n-1} \frac{a_{n-i}}{i+1} = -\frac{a_0}{n+1}$ Multiplying the first one by $\frac{n}{n+1}$ and plugging into the second gives
$a_n = \sum_{i = 1}^{n-1} \frac{n}{n+1} \cdot \frac{a_{n-i}}{i} - \frac{a_{n-i}}{i+1}>0$ by our Claim and inductive hypothesis, so we're done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

139 posts

Ywgh1

#31 h Aug 10, 2024, 8:40 PM

Y by

2006 ISL A2

We preceed with induction.
Base case is trivial.

Now look at
$\frac{a_{n-1}}{1}+\cdots+\frac{a_1}{n-1}=-\frac{a_0}{n} \text{ (1)}$
We want to show that.

$\frac{a_{n-1}}{2}+\cdots+\frac{a_1}{n}<-\frac{a_0}{n+1} \text{ (2)}$
Multiply $\frac{n-1}{n}$ to the LHS of the first equation. This will give us that the LHS of first equation is more than or equal the second one.
While for the RHS multiply by $\frac{n}{n+1}$ in order to get the RHS of the second equation.
Inductively we are done.

This post has been edited 6 times. Last edited by Ywgh1, Mar 30, 2025, 9:45 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

773 posts

#32 h Aug 30, 2024, 9:38 PM

Y by

Subjective Rating (MOHs) $\text{[math]}$

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1900 posts

#33 h Aug 31, 2024, 1:18 AM

Y by

IMO 2006 Shortlist

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1417 posts

Jndd

#34 h Sep 2, 2024, 3:54 PM

Y by

Take the equations $\sum_{k=0}^n \frac{a_{n-k}}{k+1} = 0 \text{ and } \sum_{k=0}^{n+1} \frac{a_{{n+1}-k}}{k+1} = 0$ and multiply the first by $n+1$ and the second by $n+2$ , and subtract the second equation from the first. The $a_0$ terms cancel out, and when we bring $-a_{n+1}$ to the other side of the equation, we see that the coefficients of all the other $a_i$ are of the form $\frac{n+1}{k} - \frac{n+2}{k+1}=\frac{n+1-k}{k(k+1)}$ for $k<n+1$ , which is positive. Hence, if $a_1,a_2,\ldots, a_k$ is positive for some $k$ , then so is $a_{k+1}$ . Having $a_1=\frac{1}{2}$ as the base case, this completes our induction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

799 posts

#35 h Mar 13, 2025, 10:49 PM • 1 Y

Y by OronSH

First note $a_1 = \tfrac 12$ is positive. Then for $n \ge 1$ , notice that
$(n+1) \sum_{k=0}^{n-1} \frac{a_{n-k}}{k+1} = (n+2) \sum_{k=0}^{n} \frac{a_{n+1-k}}{k+1} = -a_0$ $\implies a_{n+1} = \frac{1}{n+2} \sum_{k=0}^{n-1} a_{n-k} \cdot \underbrace{\left(\frac{n+1}{k+1} - \frac{n+2}{k+2}\right)}_{> 0}$
is positive if $a_1, \ldots, a_n$ is positive. $\blacksquare$

This post has been edited 2 times. Last edited by shendrew7, Apr 20, 2025, 9:07 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

38 posts

Bonime

#36 h Apr 13, 2025, 9:35 PM

Y by

$\textbf{A2 IMOSL 2006}$
Is it just me or is A2 easier than A1?

Just induct in $n$
If $n=1$ , $a_1+\frac{a_0}2=0 \Rightarrow a_1=\frac{1}2$ .
Supose that $a_i>0$ for all $i\leq n$ , then, we have $\sum_{k=0}^n \frac{a_{n-k}}{k+1}=0 \iff \frac{n+1}{n+2} \sum_{k=0}^n \frac{a_{n-k}}{k+1}=0$ but, $\sum_{k=0}^{n+1} \frac{a_{n+1-k}}{k+1}=0 \Rightarrow a_{n+1} + \sum_{k=1}^{n+1} (\frac{1}{k+1}-\frac{1}{k}\cdot \frac{n+1}{n+2})a_{n+1-k} = 0$ Thus we´re done because $\frac{1}{k+1}-\frac{1}{k} \cdot \frac{n+1}{n+2}\leq 0$ for all $k \leq n+1$ since $\lim_{x \rightarrow \infty} \frac{x+1}{x+2} = 1$ . $\blacksquare$

$\textit{Obs.:}$ Note that the we just use the fact that $a_0<0$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

575 posts

#37 h Apr 25, 2025, 4:31 AM

Y by

Poland has a bunch of contrived algebra LOL

We proceed by induction. The base case $n=1$ is trivial, so assume that the proposition holds for $1, 2, \cdots, n.$ For $n+1,$ observe that
$\begin{align*} \frac{1}{n+2} \sum_{k=0}^n \frac{a_{n-k}}{k+1} &= 0 = \frac{1}{n+1} \sum_{k=0}^{n+1} \frac{a_{n-k}}{k+1} \\ \implies \frac{a_{n+1}}{n+1} &= \sum_{k=1}^n a_{n-k+1} \left( \frac{1}{n+2} \cdot \frac{1}{k} - \frac{1}{n+1} \cdot \frac{1}{k+1} \right). \end{align*}$ However, as $1 \leq k \leq n,$ $\displaystyle \frac{1}{n+2} \cdot \frac{1}{k} - \frac{1}{n+1} \cdot \frac{1}{k+1} > 0 \iff (n+1)(k+1) > (n+2)k \iff n+k+1 > 2k \iff n+1 > k,$ hence each $a_i$ 's coefficient in the sum is positive so $a_{n+1} > 0.$ QED

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

674 posts

#38 h Apr 25, 2025, 3:48 PM

Y by

We prove this via induction. $a_1$ is obviously positive.

Assume $n\leq k$ are all positive. We prove that $a_{k + 1}\in \mathbb R^+.$ We have that $(k + 1)a_{k + 1} + \frac{(k + 1)a_k}{2} + \cdots + a_0 = 0 = ka_{k + 1} + \frac{ka_k}{2} + \cdots + a_0$ This ends up simiplifying so that all terms on the rhs is positive, and the left hand is $(k + 1)a_{k + 1}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1310 posts

ezpotd

#39 h May 17, 2025, 7:12 AM

Y by

Clearly we have $\sum_{k = 1}^{n} \frac{a_{n + 1 - k}}{k + 1} < \frac{n - 1}{n } \sum_{k = 0}^{n - 1} \frac{a_{n - k}}{k + 1}= \frac{n - 1}{n^2}$ , thus we have $a_{n + 1} + \frac{a_0}{n + 1} +\sum_{k = 1}^{n} \frac{a_{n + 1- k}}{k + 1} = 0$ , thus $-a_{n + 1} - \frac{a_0}{n + 1} < \frac{n - 1}{n^2}$ , giving $a_{n + 1} > \frac{1}{n^2(n + 1)}$ , as desired.

This post has been edited 1 time. Last edited by ezpotd, May 17, 2025, 7:12 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a