Proving Constant Sequence of Positive Integers Starting with n

In summary: I should have said:Assume not. That is, \exists{n} and \exists{k} (where n and k are positive integers), {\sum}^k_{i=1}{a_i}=Ck for some C\geq{k}.That is, there exists an n and there exists a k such that the sum up to the kth term is a multiple of k. Sorry for the confusion.
  • #1
Feldoh
1,342
3
Let [itex]n[/itex] be a positive integer. Define a sequence by setting [itex]a_1 = n[/itex] and, for each [itex]k > 1[/itex], letting [itex]a_k[/itex] be the unique integer in the range [tex]0 \le a_k \le k-1[/itex] for which [itex]\displaystyle a_1 + a_2 + \cdots + a_k[/itex] is divisible by [itex]k[/itex]. For instance, when [itex]n = 9[/itex] the obtained sequence is [itex]\displaystyle 9, 1, 2, 0, 3, 3, 3, \ldots[/itex]. Prove that for any n the sequence [itex]\displaystyle a_1, a_2, a_3, \ldots[/itex] eventually becomes constant.
 
Physics news on Phys.org
  • #2
that's cool, where'd you find this?
 
  • #3
Thanks, that was fun! I too would like to know where you found this problem!

Here is my attempt at a solution:

It is clear that once [tex]{\sum}^k_{i=1}{a_i}=ck[/tex] for some c<k, subsequent terms in the sequence simply require additional c's to be added to them. Thus, we need to prove that for any starting n, there exists a k such that [tex]{\sum}^k_{i=1}{a_i}=ck[/tex] for some c<k.

Assume not. That is, [tex]\forall{n}[/tex] and [tex]\forall{k}[/tex] (where n and k are positive integers), [tex]{\sum}^k_{i=1}{a_i}=Ck[/tex] for some [tex]C\geq{k}[/tex].

Then we have

[tex]{k}^{2}\leq{Ck}=n+{a_2}+{a_3}+...+{a_k}\leq{n+1+2+...+(k-1)}={n+\frac{k(k+1)}{2}}=\frac{2n+k^{2}-k}{2}}[/tex]

So by letting [tex]{n}\geq{\frac{k^{2}+k}{2}}[/tex] for an arbitrary k, we derive a contradiction, for the sequence starting with n converges by the kth term. This completes the proof.



Is this correct?
 
  • #4
There is one flaw in the proof, mainly I think to do with how you've written it: n is fixed, you can't choose n; it doesn't make sense to say "let n be greater than (k^2+k)/2 for an arbitrary k".

It is also an unnecessary proof by contradiction. It suffices to note that given any n then for k sufficiently large n + k(k-1)/2 is less than k^2.
 
  • #5
Aaah, I see what you mean. Thanks for the correction!
 
  • #6
haha, that's a usa math olympiad question. ah, reminds me of the good old days. looking forward to putnam in college
 
  • #7
Feldoh said:
Let [itex]n[/itex] be a positive integer. Define a sequence by setting [itex]a_1 = n[/itex] and, for each [itex]k > 1[/itex], letting [itex]a_k[/itex] be the unique integer in the range [tex]0 \le a_k \le k-1[/itex] for which [itex]\displaystyle a_1 + a_2 + \cdots + a_k[/itex] is divisible by [itex]k[/itex]. For instance, when [itex]n = 9[/itex] the obtained sequence is [itex]\displaystyle 9, 1, 2, 0, 3, 3, 3, \ldots[/itex]. Prove that for any n the sequence [itex]\displaystyle a_1, a_2, a_3, \ldots[/itex] eventually becomes constant.
define A(n) to be the least common multiple of the set {1,2,3...n}
A(n) = {1,2,6,12,60,420,...}
I noticed that if [tex]A_{m-1} < n \le A_{m}[/tex] then [tex]{\sum}^k_{i=1}{a_i} \geq \frac{kA_{m}}{m}[/tex] and [tex]a_{i}[/tex] converges to [tex]\frac{A_{m}}{m}[/tex] by the value of k equal to m. I thought I had a proof but need to come back to this later.
 
  • #8
matticus said:
that's cool, where'd you find this?

It's actually from 2007 USA Mathematics Olympiad.

I found them here the solutions are there too. I had a lot of fun with the first one so I though I'd post it :biggrin:
http://www.artofproblemsolving.com/Wiki/index.php/2007_USAMO [Broken]
 
Last edited by a moderator:
  • #9
matt grime said:
There is one flaw in the proof, mainly I think to do with how you've written it: n is fixed, you can't choose n; it doesn't make sense to say "let n be greater than (k^2+k)/2 for an arbitrary k".

It is also an unnecessary proof by contradiction. It suffices to note that given any n then for k sufficiently large n + k(k-1)/2 is less than k^2.

As I was falling asleep just now, this problem popped into my head, and I realized that I made an extremely stupid error, and if I had not made that error, I would have never made the mistake you pointed out (and I would have, presumably, had a wholly correct proof).

The error? I stated the negation incorrectly...I said "for all n" when I should have said "there exists an n". What a silly mistake. Oh well, its summer, I need to get these bloopers out of my system before the semester begins :rolleyes:
 
  • #10
abelian jeff said:
The error? I stated the negation incorrectly...I said "for all n" when I should have said "there exists an n".

No you shouldn't. n is given to you in the question. k is what you play with.
 
  • #11
Yes, it turns out that all you need to work with is the k. However, I said this:

Assume not. That is, [tex]\forall{n}[/tex] and [tex]\forall{k}[/tex] (where n and k are positive integers), [tex]{\sum}^k_{i=1}{a_i}=Ck[/tex] for some [tex]C\geq{k}[/tex].

That is clearly incorrect.
 

1. What is a constant sequence of positive integers starting with n?

A constant sequence of positive integers starting with n is a sequence of numbers where each number is equal to the previous number plus a constant value. For example, if n = 3, the sequence would be 3, 4, 5, 6, 7, etc.

2. How do you prove that a sequence is constant?

To prove that a sequence is constant, you must show that the difference between each consecutive term is the same. This can be done by subtracting any two consecutive terms and comparing the result to the difference between the next two terms. If the difference is the same, then the sequence is constant.

3. Can a constant sequence have negative numbers?

Yes, a constant sequence can have negative numbers. The key is that the difference between each consecutive term must still be the same.

4. How do you start proving a constant sequence of positive integers starting with n?

To start proving a constant sequence of positive integers starting with n, you must first write out the sequence and determine the difference between each consecutive term. If the difference is the same, you can then use mathematical induction to prove that the sequence is constant.

5. Why is proving a constant sequence of positive integers starting with n important in science?

Proving a constant sequence of positive integers starting with n is important in science because it allows us to make predictions and conclusions based on patterns and relationships between numbers. This can be useful in various fields such as physics, chemistry, and biology.

Similar threads

  • Linear and Abstract Algebra
Replies
10
Views
2K
  • Linear and Abstract Algebra
Replies
4
Views
962
  • Linear and Abstract Algebra
Replies
4
Views
897
  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
694
  • Linear and Abstract Algebra
Replies
15
Views
4K
  • Linear and Abstract Algebra
Replies
10
Views
2K
  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
934
Replies
1
Views
639
Back
Top