4
$\begingroup$

Question:

Prove or disprove: there exists a unique positive integer sequence $\{a_{n}\}$ satisfying the following condition:

$\forall m\in N^{+}$, there exists a unique integer sequence $\{b_{i,m}\},i=1,2,\cdots,m$, such that $$|b_{i,m}|\le i$$ for $i=1,2,\cdots,m$, and $$m=\sum_{i=1}^{m}\left(a_{i}\cdot b_{i,m}\right)$$

Question: does there exist a sequence $\{a_{n}\}$ that satisfies this condition?

I can't find a solution. Can someone find one? This problem is from Peking University Middle school students' mathematics Olympic problem 3. I found this problem is similar this interesting problem. So I guess this problem was maybe created by Paul Erdös?

$\endgroup$
  • $\begingroup$ OK, since my edits seem to keep getting rejected, the last part should be "I've spent lots of time looking for a counterexample but didn't find one. Can someone maybe find one?", have "High School" (gāo zhōng), have "similar to" and end with "I feel this problem looks like it was brought up by Erdös, is that right?". Will this comment be deleted too? $\endgroup$ – MickG Aug 17 '14 at 16:41
  • $\begingroup$ Yeah I guess you're right, but since my plan was to edit the question the comments weren't meant to raise interest. I can help you communicate with other users who will speak English, but I think these comments can be left in place. If you upvote this one, it might be shown rather than hidden, so please do so. By the way, "upvote" means "click the upward pointing triangle that appears on the left of the comment when you put your cursor on it" :). $\endgroup$ – MickG Aug 17 '14 at 16:45
  • $\begingroup$ And I'm afraid I cannot answer this question. :) $\endgroup$ – MickG Aug 17 '14 at 16:46
  • $\begingroup$ I deleted the comments since the edit in question had been rejected. If anyone wonders what is going on here, me and the OP had a few comments in Chinese which the first comment takes into account, together with the "unique" I added (which was added by someone else's edit too) before the sequence $b_{i,m}$. What I left, I left because it was in English. What I deleted was almost all in Chinese. $\endgroup$ – MickG Aug 17 '14 at 19:43
  • $\begingroup$ Exactly why won't a tag to math110 appear? I keep trying to edit the previous comment to include it, and it invariably disappears, as if the edit was ignored. $\endgroup$ – MickG Aug 17 '14 at 19:45
2
+25
$\begingroup$

A sequence exists.

Define $a_1 = 1$, and $ a_n$ recursively as

$$ a_n = 1 + 2 \sum_{i=1}^{n-1} i a_i. $$

For example, we get
$ a_2 = 1 + 2 \times (1\times 1) = 3$,
$a_3 = 1 + 2 \times ( 1 \times 1 + 2\times 3) = 15$,
$a_4 = 1 + 2 \times ( 1 \times 1 + 2 \times 3 + 3 \times 15 ) = 105$.

For the first few terms of $m$, we have
$\begin{array}{llll} 1 & = 1 \times 1 & &\\ 2 &= (-1) \times 1 &+ 1 \times 3 \\ 3 &= 0 \times 1 &+ 1 \times 3\\ 4 &= 1 \times 1 &+ 1 \times 3\\ 5 &= (-1) \times 1 &+ 2 \times 3\\ 6 &= 0 \times 1 &+ 2 \times 3\\ 7 &= 1 \times 1 &+ 2 \times 3\\ 8 &= (-1) \times 1 &+ (-2) \times 3 &+ 1 \times 15\\ 9 & = 0 \times 1 & + (-2) \times 3 & + 1 \times 15 \\ \end{array}$

(Is there a pattern? You bet! We're just building the next "block" of terms from the previous.)

We will show that this sequence satisfies the conditions.

Lemma 1: Fix $m$. If for some $K$, $m + \sum_{i=1}^{k-1} i a_i < a_K$, then $b_{K,m} = 0 $.

It suffices to prove this for the largest value of $K$, and then induct downwards. From the construction of the sequence $a_i$, $b_{K,m}$ must be positive. Then, we cannot subtract off enough in $\sum -i a_i$ to reach $m$. Explicitly, we have

$$ \sum{ b_{i,m} a_i} \geq a_K - \sum_{i=1}^{K-1} i a_i > m . _\square $$

Lemma 2: Fix $m$. For the largest $K$ such that, $m + \sum_{i=1}^{K-1} i a_i \geq a_K$, then $b_{K,m} = \lfloor \frac{ m + \sum_{i=1}^{K-1} i a_i}{ a_K } \rfloor $.

Since it is the largest $K$, Lemma 1 tells us that the coefficients of higher terms are all 0. Hence, this coefficient must be positive. If $b_{K,m}$ is not large enough, then you cannot make the sum large enough. Conversely, if $b_{K,m}$ is not small enough, then you cannot make the sum small enough. Explicitly, we get that $$ - \sum_{i=1}^{K-1} i a_i \leq m - b_{K,m} a_K \leq \sum_{i=1}^{K-1} i a_i, $$ $$ m - a_K + \sum_{i=1}^{K-1} i a_i < m - \sum_{i=1}^{K-1} i a_i \leq b_{K,m} a_K \leq m + \sum_{i=1}^{K-1} i a_i $$

The result follow by dividing by $a_K$. $_\square$

Proof of existence and existence: Apply Lemma 1 to determine the first non-zero coefficient $b_{K,m}$. Apply Lemma 2 to determine $b_{K,m}$, which is unique. Apply induction to $m' = m - b_{K,m} a_K$.


Note: OEIS informs me that this is the sequence of double factorial of odd numbers. I currently don't see how this fact lends itself to the solution, but that is very suspicious to me, especially when thinking in bases. However, I wasn't able to push through thinking on that front, but I believe that is valuable in understanding this question.

My suspicion is that this sequence $a_i$ is unique. However, it relies on the constructive approach, where I have a ton of $b_{i,m} = 0$. It's not obviously clear to me why we cannot allow for massive cancellations somehow.

Rough working. Suppose $a^* _i$ is another sequence that satisfies the condition.
1) We will show that $a^*_i$ is an increasing sequence.
2) We will show that $ a^*_i \geq a_i$.

$\endgroup$
  • 2
    $\begingroup$ Hmm, yeah it's not clear to me the sequence is unique... $\endgroup$ – user7530 Aug 23 '14 at 23:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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