An Odd Fact

[superprismatic]

For an integer n≥2, let O_n = {1,3,5,...,2n-1}. Prove that

n²-2 cannot be written as a sum of distict elements of O_n.

[curr3nt]

The sum of O_n is equal to n².

Since 2 is not within O_n there is no way to get n²-2. The closest possible would be n²-1 or n²-3.

[jim]

I would like to propose an extension of this problem. Same conditions. Show every number from one to n squared can be expressed as a sum of distinct odd integers from 1 to 2n-1 except for the numbers 2 and n squared - 2

[EventHorizon]

I would like to propose an extension of this problem. Same conditions. Show every number from one to n squared can be expressed as a sum of distinct odd integers from 1 to 2n-1 except for the numbers 2 and n squared - 2

First, an obvious symmetry. Since they all sum to n^2, if you can show x as a sum of distinct odd integers from 1 to 2n-1, then n-x is simply the sum of all the other integers besides those used to sum to x.

This means if I prove I can find sums for the first half of them, I can find sums for the second half based on the sums from the first half.

For the odd numbers up to 2n-1, obviously you have the number already in the set.

For the even numbers up to 2n, the odd number just below it is in the set, so add in 1. This doesn't work for getting 2 due to the distinct element restriction.

If I add in 2n-1 to all those sums (except the two that used 2n-1), I can get all the way up to 4n-3, except for the value 2n-1+2=2n+1, due to not being able to get a sum for 2. Ignore this for now.

If I add in the 2n-1 and 2n-3 to all the sums from 1 to 2n-4, I can get all the way to <doesn't really matter for the proof> while missing only 2n-1+2n-3+2=4n-2.

Using this pattern of adding in the next largest element will work, but gives us a sequence of missed numbers. This sequence is easy to find a sum for as follows:

(2n-1)+2 = (2n-3)+3+1

(2n-1)+(2n-3)+2 = (2n-1)+(2n-5)+3+1

etc

So I take the smallest one included and use the next smallest. This gives a difference of 4 to make up... which 1 and 3 will do.

The problem occurs when the smallest element included is 5, since this would require two 3's.

For n>3, I've already passed halfway, so I can use the first thing I showed to give sums for the rest (except for n^2-2, which there isn't one for as shown by curr3nt).

So I simply need to show it works for 0<n<=3.

n=1

{1} for 1

n=2

{1} for 1

none for 2, which in this case is the same as n^2-2

{3} for 3

{1,3} for 4

n=3

{1} for 3

none for 2

{3} for 3

{1,3} for 4

{5} for 5

{1,5} for 6

none for 7 since 3^2-2=7

{3,5} for 8

{1,3,5} for 9

I should probably include that summing no elements results in a sum of 0, and summing them all gives n^2.

A proof of the latter is achieved by pairing up the elements into pairs that sum to 2n, and seeing how many pairs there are.

For even numbers, there are n/2 pairs. n/2 * 2n = n^2.

For odd numbers there are (n-1)/2 pairs and one element left.... which is n itself. (n-1)/2 * 2n + n = n(n-1) + n = n^2 - n + n = n^2.

[jim]

Event Horizon--

I think your proof is essentially the same as mine, but formulated in a different fashion.

I basically used induction. We can do 3=3 and 4=3+1. Let m be the smallest number greater than 2 which we cannot do. It must be at least 5 so m-2 is at least 3 and as a smaller number greater than 2 we can do it. We adjust the solution for m-2 by increasing one of the odd numbers by two, replacing it with an odd nuimber not already included in the set of m-2. Since the solution for m-2 is not the null set, we can always do this unless the solution for m-2 is of the form U(j) which is all the allowable odd numbers from j upwards for some j less than or equal to 2n-1. But in this case we can replace j with 1 and 3 and j-2 which we can always do as long as j>5. If j=5 we get our sum m-2 = n^2 - 4 so m = n^2 -2 which is in fact the smallest non-solution except for 2. j=3 and j=1 give us m-2 = n^2 -1 and n^2 which in either case give us m> n^2 which we can also not do because they are too large.