## A hard but fascinating Math problem

I ran into the following problem in a contest problem book. I won't reveal the source until later. I was not able to solve this problem and even though the solution is in the back of the book so I know how to solve it now, I'd like to see if anyone can solve this in an elegant and intuitive way and maybe even show how the author might have invented this problem.

There's no prize for solving this, but I will publish all solutions and give link love to all solvers, and I will give special kudos to anyone who can help me to see why the interesting property shown in this problem is true.

Here's the problem:

Express an arbitrary positive integer n, as ordered sums of positive integers in 2^(n-1) ways. For example, if n=5, the 16 ordered sums are listed in the left column below:

5 2(=2)

4+1 2x1(=2)

1+4 1x2(=2)

3+2 2x3(=6)

2+3 3x2(=6)

3+1+1 2x1x1(=2)

1+3+1 1x2x1(=2)

1+1+3 1x1x2(=2)

2+2+1 3x3x1(=9)

2+1+2 3x1x3(=9)

1+2+2 1x3x3(=9)

2+1+1+1 3x1x1x1(=3)

1+2+1+1 1x3x1x1(=3)

1+1+2+1 1x1x3x1(=3)

1+1+1+2 1x1x1x3(=3)

1+1+!+1+1 1x1x1x1x1(=1)The entries in the right column are obtained from the corresponding entries in the left column by changing (a) additions to multiplications and (b) all the integers greater than or equal to 3 to 2, (c) 2 to 3, (d) 1 to 1 (i.e., keeping 1 unchanged).

Now add all the products in the right column. For n=5, we obtain

2+2+2+6+6+2+2+2+9+9+9+3+3+3+3+1=64=8^2

Prove or disprove: For every positive integer n, the sum of all the products in the right column is always a perfect square.

Send your solutions to sol dot lederman at gmail dot com.

sam shahApril 5th, 2008 - 16:19

This is a frustrating (but good) problem! I hate that I know I’m over halfway to the solution but my brain is sloggy and doesn’t want to make that all important conceptual leap… Yargh.

FlorianApril 5th, 2008 - 17:20

Thanks for the great challenge!

My solution is based on finding

a recursion to derive the 2^(n-1)

ordered sums of n from those of n-1.

Based on this imtermediate result

I derived anoter recursion that

calculates sum of the products

in the right column.

But I’m not going to spoil your fun

here with the full solution. Just

a hint:

The sum of the products of the right

column equals the n-th Fibonacci

number suqared. The Fibonacci

sequence is 1,2,3,5,8,13,…

n => Sum of products in the right Column

1 => 1^2 = 1 a perfect square

2 => 2^2 = 4 a perfect square

3 => 3^2 = 9 a perfect square

4 => 5^2 = 25 a perfect square

5 => 8^2 = 64 a perfect square

…

Sjoerd VisscherApril 7th, 2008 - 06:42

Some observations following Florian:

SP(n) = F(n+1)^2

SP(n) – SP(n-1) = F(n+1)^2 – F(n)^2 = (F(n+1) – F(n))(F(n+1) + F(n)) = F(n-1)F(n+2)

SP(2) – SP(1) = 4 – 1 = F(1)F(4) = 1 * 3 = 3

SP(3) – SP(2) = 9 – 4 = F(2)F(5) = 1 * 5 = 5

SP(4) – SP(3) = 25 – 9 = F(3)F(6) = 2 * 8 = 7 + 9

SP(5) – SP(4) = 64 – 25 = F(4)F(7) = 3 * 13 = 11 + 13 + 15

SP(6) – SP(5) = 169 – 64 = F(5)F(8) = 5 * 21 = 17 + 19 + 21 + 23 + 25

SP(7) – SP(6) = 441 – 169 = F(6)F(9) = 8 * 34 = 27 + 29 + 31 + 33 + 35 + 37 + 39 + 41

Notice that on the right you get all uneven numbers (as expected when looking at differences of squares).

AnonymousJune 23rd, 2008 - 14:13

duh

PaidomJanuary 12th, 2010 - 15:58

When n=2 the sum of products(sop) will be (2+0)^2 = 4

When n=3 the sop will be (3+0)^2 = 9

When n=4 the sop will be (4+1)^2 = 25

When n=5 the sop will be (5+3)^2 = 64

When n=6 the sop will be (6+7)^2 = 169

When n=7 the sop will be (7+15)^2 = 484

Let our equation for sop then be:

(n+i)^2 = sop

i is the number that n must be increased by to equal the square root of the sop of n.

(n+i will always equal a Fibonacci number, as mention by Florian in an above post)

Now let c = n-3 but never equal less than 0.

As n increases by 1, i increases by 2^c.

exampl:

(4+1)^2 to (5+3)^2

i=1 to i=3

increases by 2

2^c = 2^(n-3)

2^1 = 2^(4-3) = 2

We can now find the sop of n without having to right out each combonation to get a sum of n, converting those to get products and then adding those products.

If n=8, i = 15 + 2^(8-3) = 47

Giving (8 + 47)^2 = sop = 3025

So if you have the i value of one sop equation, you can find the i value of the next or previous sop equation as follows.

next:

if (n + i)^2

then ([n+1] + [i + 2^(n-2)])^2

previous:

if (n + i)^2

then ([n-1] + [i - 2^(n-4)])^2

The drawback to this method is that you must know the previous or next i value, in order to solve for the current i value forcing you to do each and every sop equation leading up to the answer you desire.

However this method can be much more easily programed, and you can let a computer to do the numerous calculations for you.

I think that this proves the theory that the sop of n will always be a perfect square for all posative values of n as long as c or (n-3) never equals a negative number, and (n + i)^2 is equal to the sop of n which I have proven for n = 3 through n = 8.

WagsApril 8th, 2010 - 10:28

Hey guys, I just found this page today while browsing around for some brain candy, not sure if anyone is working on this or not still. But both Sjoerd and Paidom had similar ideas to different parts of my solution. I don’t want to give it completely away, but first prove that the nth term formula can be written as [2^(n-3)]+n-1, (for all n > 3), (Hint: use you’re old pal induction) then show that sqrt([2^(n-3)]+n-1) = F(n+1) and you’re done.