Mathematics Journal, Proof for


by TimNguyen
Tags: journal, mathematics, proof
TimNguyen
TimNguyen is offline
#1
Sep26-05, 11:25 PM
P: 81
Hello.

I was reading a journal and an interesting problem came up. I believe the journal was in the American Mathematics Society publications. Well, here's the statement.

"For all integers, n greater than or equal to 3, the number of compositions of n into relatively prime parts is a multiple of 3."

Example : For 4: the compositions of relatively prime parts are:

(1,3), (3,1), (2,1,1), (1,2,1), (1,1,2), (1,1,1,1).

This is what I have so far for a "proof":

Let n be an integer greater than or equal to 3.
Then the first composition will be given by (n-1, 1), (1, n-1); since for all k, an integer, (k, 1) and (1, k) are always relatively prime.
Also, (1, 1, ..., 1) where the composition adds to n is also an obtainable composition.

(So basically, I've gotten the end points of the compositions to be a multiple of 3, then I need to prove that the "in-between" compositions will also be a multiple of 3.)

Well, obviously I'm stuck there. I've tried to split it into two cases afterwards where the cases involve n - odd and n - even but it has come to no avail. Also I've tried to find a formula where the compositions of relatively prime parts is a multiple of 3 but it fails at "6". Here was the formula I came up with that failed, if it could be potentially be improved upon.

Formula: Starting at n=1, where i=3, i being the starting point.

(i)!/2^n

Like:
For 3, 3! = 6 divided by 2^1 = 2 will equal 3 compositions- a multiple of 3
For 4, 4! = 24 divided by 2^2 = 4 will equal 6 compositions - a multiple of 3
For 5, 5! = 120 divided by 2^3 = 8 will equal 15 compositions - multiple of 3

Well, hopefully people will post their ideas...
Phys.Org News Partner Science news on Phys.org
Going nuts? Turkey looks to pistachios to heat new eco-city
Space-tested fluid flow concept advances infectious disease diagnoses
SpaceX launches supplies to space station (Update)
TimNguyen
TimNguyen is offline
#2
Sep29-05, 02:42 AM
P: 81
Any algebraist in here that could help?
TimNguyen
TimNguyen is offline
#3
Oct8-05, 04:22 AM
P: 81
Well, I've still been trying to prove this for the past week. I think there may be some recursion sequence or something. Well, I've tried listing the compositions and here's the results:

n=3 : 3 compositions
n=4 : 6 compositions
n=5 : 15 compositions
n=6 : 27 compositions
n=7 : 63 compositions
n=8 : 129 compositions

I'm predicting that n=9 : 387 compositions
n=10 : 687 compositions

Anyone feel like lending a hand...?

VietDao29
VietDao29 is offline
#4
Oct8-05, 05:07 AM
HW Helper
VietDao29's Avatar
P: 1,422

Mathematics Journal, Proof for


Maybe I don't really get what you mean... But for n = 5, I get 10 compositions, which means it fails for n = 5.
n = 5:
(1, 4), (4, 1)
(1, 1, 3), (1, 3, 1), (3, 1, 1)
(1, 1, 1, 2), (1, 1, 2, 1), (1, 2, 1, 1), (2, 1, 1, 1)
(1, 1, 1, 1, 1)
That's 2 + 3 + 4 + 1 = 10...
Viet Dao,
TimNguyen
TimNguyen is offline
#5
Oct9-05, 04:47 AM
P: 81
Quote Quote by VietDao29
Maybe I don't really get what you mean... But for n = 5, I get 10 compositions, which means it fails for n = 5.
n = 5:
(1, 4), (4, 1)
(1, 1, 3), (1, 3, 1), (3, 1, 1)
(1, 1, 1, 2), (1, 1, 2, 1), (1, 2, 1, 1), (2, 1, 1, 1)
(1, 1, 1, 1, 1)
That's 2 + 3 + 4 + 1 = 10...
Viet Dao,
You're forgetting:
(3,2), (2,3), (2,2,1), (2,1,2), (1,2,2),

which adds to 15.


Register to reply

Related Discussions
Discrete Mathematics Absolute Value Proof Calculus & Beyond Homework 3
Mathematics by proof General Math 4
journal access Atomic, Solid State, Comp. Physics 2
My Journal of Basic Concepts of Mathematics Calculus 30
A Mathematics Proof Book Calculus 13