## Round 5: Problem 4

Let be an infinite arithmetic progression of positive integers with the special property that the sum of the first n terms of is a perfect square for all n. If 2009 is the k-th term of the sequence, how small can k be?

Advertisements

***Partial Solution***

21. It’s the 21st term in the sequence (http://img222.imageshack.us/my.php?image=5c14cd19d73c648a4b6b2ce.png) when i=20. I claimed that every such arithmetic progression which had that requirement about squares had to be derived from the summation of all consecutive odd natural numbers (whose partial prefix sums (making that up) were every square). Also, because the first term, being a square, could not be negative, and because squares in general are nonnegative, that meant all terms were positive.

This severely restricts 2009 (7*7*41): it had to be the sum of m consecutive odd numbers, and since the first term was a square and had to be the sum of the smallest m distinct odd numbers, blah blah blah only one possibility (“blah blah blah” meaning “exercise left to the reader” (“exercise left to the reader” means “I think I can do it if I try hard enough, but I’m being lazy and also have homework to do”)).

Franklin LeeMay 11, 2009 at 22:17

k = 2,

let a1 = 16, then

a1 = 16, a1 + a2 = 16 + 2009 = 2025 = 45^2.

It’s easy to construct an infinite sequence

let a3 – (a1 + a2) = 90^2 – 45^2,

let a4 – (a1 + a2 + a3) = 180^2 – 90^2,

and so on

anonymousMay 13, 2009 at 18:14

I think a lot of people got it wrong because they assumed “arithmetic progression” (http://en.wikipedia.org/wiki/Arithmetic_progression) couldn’t mean what they thought it meant, so they just assumed it meant “sequence”. I assumed too, but later on during the test I wasn’t sure and asked a proctor.

In an arithmetic progression, a_{i+1} – a_{i} = a_{j} – a_{j+1} for all i and j. Your a_4 – a_3 = 180^2 – 45^2, and your a_2 – a_1 = 45^2 – 4^2.

Franklin LeeMay 13, 2009 at 21:57

Sorry. Correction:

In an arithmetic progression, a_{i+1} – a_{i} = a_{j+1} – a_{j} for all i and j.

Franklin LeeMay 13, 2009 at 22:01

I can prove that an arithmetic progression such that partial sums are squares has to be of the form n^2 times the odd numbers, but I’d never have come up with it in a 3 hour time restriction.

jimMay 16, 2009 at 11:27

k=1004

A set of perfect squares, call it S, is

S={1,4,9,16,25,36…}

but,

1=1

4=1+3

9=1+3+5

16=1+3+5+7

….

Make a new set with the partial sums, S’={1,3,5,7…} with

S’[0]=1, S’[1]=3… then,

S’[k]=S’[k-1]+2

=S’[k-2]+2+2

=S’[k-3]+2+2+2

…

=S’[k-k]+2k

=1+2k=2009 => k=1004

CourantFebruary 12, 2010 at 03:39

btw define S’[0]=1

CourantFebruary 12, 2010 at 03:42

The correct answer is 21, and is achieved by the sequence a_k=49(2k-1).

To get this, note that if $f(n)$ denotes the sum of the first n terms, f(n) must be a perfect square polynomial in n (because it is a square at every natural number), so f(n)=(an+b)^2 for some integers a, b.

at the same time, let the sequence be r, r+d, …. summing the first n terms gives (d/2)n^2+(r-d/2)n, and comparing coefficients with those of (an+b)^2, we get that b=0 and d=2r, where r is a perfect square, say r=k^2. Thus the sequence has the form k^2, 3k^2, 5k^2, … as *jim* already pointed out. the rest is easy…

MEMarch 26, 2010 at 16:02