A math challenge

[ElijahJones]

I thought to put this thread in the challenge area but it is math and all that stuff seems like philosophy. So here goes. I apologize for the pseudo-code but I do not have latex.

 

Challenge 1:

 

Prove that if n+1=(m+1)(s+1)

 

then sum(a^k,k=0..n)=sum(a^[k*m+1],k=0..s)*sum(a^k,k=0..m)

 

Challenge 2:

 

Show that if n is odd then

 

limit(a->infinity, ln[a](sum(a^k,k=0..n))-ln[a](sum(a^2k,k=0..[n-1]/2))) = 1

 

Challenge 3:

 

Define an invertible function psi taking the set

 

{limit(a->infinity,ln[a](sum(a^k,k=0..n))),

limit(a->infinity,ln[a](sum(a^2k,k=0..[n-1]/2)))|n=1...infinity}

 

to the natural numbers.

 

Challenge 4:

 

Explain what this means!

[ElijahJones]

(I missed a pair of parentheses)

 

I thought to put this thread in the challenge area but it is math and all that stuff seems like philosophy. So here goes. I apologize for the pseudo-code but I do not have latex.

 

Challenge 1:

 

Prove that if n+1=(m+1)(s+1)

 

then sum(a^k,k=0..n)=sum(a^[k*(m+1)],k=0..s)*sum(a^k,k=0..m)

 

Challenge 2:

 

Show that if n is odd then

 

limit(a->infinity, ln[a](sum(a^k,k=0..n))-ln[a](sum(a^2k,k=0..[n-1]/2))) = 1

 

Challenge 3:

 

Define an invertible function psi taking the set

 

{limit(a->infinity,ln[a](sum(a^k,k=0..n))),

limit(a->infinity,ln[a](sum(a^2k,k=0..[n-1]/2)))|n=1...infinity}

 

to the natural numbers.

 

Challenge 4:

 

Explain what this means!

[mezarashi]

I'd like to take up Challange #4, and here is my answer:

 

"this" is an English pronoun. In its main usage, it is:

 

1. Used to refer to the person or thing present, nearby, or just mentioned: This is my cat. These are my tools.

2. Used to refer to what is about to be said: Now don't laugh when you hear this.

3. Used to refer to the present event, action, or time: said he'd be back before this.

2. Used to indicate the nearer or the more immediate one: This is mine and that is yours.

 

Source: The American Heritage® Dictionary of the English Language, Fourth Edition

[ElijahJones]

Cute! But really its not as daunting as it seems in fact #4 is really the hardest one of the bunch and the this refers to the answers to challenges 1-3 Mr. Clinton. It is not a debate about what the deifinition of "is" is.

 

[ydoaPs]

(I missed a pair of parentheses)

 

I thought to put this thread in the challenge area but it is math and all that stuff seems like philosophy. So here goes. I apologize for the pseudo-code but I do not have latex.

we all can use [math]\LaTeX[/math] use the math tags

[ElijahJones]

Math tags? Something new to learn. [MATH] 2+2=1 mod 3[/MATH] That does not seem to work. Would you be willing to help me get started?

[ElijahJones]

oh it does work, nifty. Let me tryot get the first challenge in latex.

 

[MATH]sum(a^i,0..n)[/MATH]

[ElijahJones]

[MATH]sum[a^1,0..n][/MATH]

[ElijahJones]

Show that if [MATH]n+1=(s+1)(m+1)[/MATH] then

 

[MATH]\sum_{i=0}^{n}a^{i}=\sum_{i=0}^{s}a^{i(m+1)}\sum_{i=0}^{m}a^{i}[/MATH]

 

for any natural number [MATH]a[/MATH].

[ydoaPs]

[MATH']$\Sigma$_{i=0}^{n}[/MATH]

instead of "$/Sigma$_{i=0}^{n}", use "/sum_{i=0}^{n}" like this: [math]\sum_{i=0}^{n}[/math]

[ElijahJones]

Thank you Shelbyville!

[Algebracus]

Challenge 1:

 

In most cases we can rewrite this as (a^(n + 1) - 1)/(a - 1) = (a^(m + 1)(s + 1) - 1)/(a^(m + 1) - 1) * (a^(m + 1) - 1)/(a - 1), which surely is true. There are two cases left: a - 1 = 0 and/or a^(m + 1) = 1.

 

Case I: a = 1. The expression is simply (n + 1) = (s + 1)(m + 1).

 

Case II: a = -1 and m is odd. Now n also is odd, so both 1 + (-1) + (-1) + ... + (-1)^n and 1 + (-1) + (-1) + ... + (-1)^m are zero, and the result follows.

[ElijahJones]

Challenge 1:

 

In most cases we can rewrite this as (a^(n + 1) - 1)/(a - 1) = (a^(m + 1)(s + 1) - 1)/(a^(m + 1) - 1) * (a^(m + 1) - 1)/(a - 1)' date=' which surely is true. [/quote']

 

You are starting to prove theorems like an Englishman. That's not a proof my friend. Now you have to prove that statement, its easier the other way trust me. 'Which is surely true' come on now! That's as bad as saying 'Obviously a implies b'. Remember I have proved this result myself I know what it takes. I'll give you a hint (ganted there may be other versions but I have one) you need to use the pidgeon hole argument. Ok, I'll give you a big hint. Go back to the summation formula and show that the powers produced on the left are the same as the ones you get by expanding the right. Show that the smallest power appearing on both sides is zero and the greatest is n. Next you need show that the right hand side produces exactly n+1 unique powers when expanded (this is the tricky part). once you have that you have pidgeon holed the solution, then you can say 'Since the powers appearing on both sides are exactly the set {0,1,2,....,n} 'obviously' the expressions are equal.'

 

[Algebracus]

I used the formula for a geometric series to show the result in most cases, except those cases where the formula implie a division by 0. Then I checked the cases which where left. Although you by some reason say the opposite, I really think a/b * b/c = a/c is obvious!

 

It doesn't seem like you have heard about the formula for geometric series, but here it comes (with a huge hint for how to derive it):

 

S = 1 + a + a^2 + ... + a^n

aS = a + a^2 + ... + a^(n + 1)

S = (a^(n+1) - 1)/(a - 1).

 

 

"You are starting to prove theorems like an Englishman". What do you mean by this??!

[ElijahJones]

The equation sum(a^1,i=0 to n)=(a^(n+1)-1)/(a-1) is not the same as the euqation I wrote above. Look at it carefully and you will see this to be true. You can substitute your factorization of the gemoetric sequence (which everyone knows by the way) for the sum on the left but the fact remains that the formula I present is factorization formula with far reaching implications and it is related to the cyclotomic polynomials.

 

Look again at the formula. It is a factorization of the geometric series while the standard formula for the sum of a gemeotric series is rather a factorization of the term a^(n+1)-1. In fact the standard formula tells us that a-1 always divides a^(n+1)-1 for a>1 and is a result applicable to the real numbers. I am only considering my formula in relation to integral values of a greater than or equal to 1. Notice that in my formula if a equals one we reduce to the familiar multiplication tables for integers. This suggests that the result is somehow an extension of the familiar multiplicative structure on the integers, which in fact it is. The difficulties in extending it further have to do with the notion of the outer product, polynomial multiplication, and information that is lost in that step. But I am working on some p.d.f's and algorithms that will look into that. The fastest way to factor any number is going to be in base two and at best you are going to get log time, this seems to follow from the theorem when a=2.

 

Consider this for odd integer N and in base 2,

 

N = (2x[1]+1)(2y[1]+1)

 

Suppose x[1] and y[1] are two big to guess simply, then write

 

x[1]=2x[2]+1 or x[1] = 2x[2]

y[1]=2y[2]+1 or y[1] = 2y[1]

 

There are four choices of form then for the ordered pair (x[2],y[2]) but for all of them x[2] <= x[1]/2 and y[2] <= y[1]/2 so the algorithm will end in Log[2](N) steps but because we have no way of guessing which of the choices searching the treee of possibilities quickly becomes untenable for large N. The formula I gave here defines those polynomials in a for which the process is simple because polynomial multiplication proceeds in a special way.

 

Hope that helps.