Challenge

(probably simple, but I found it interesting)

Discuss the language of the universe.

Moderators: Calilasseia, ADParker

Challenge

#1  Postby scott1328 » Nov 14, 2019 5:14 pm

Show that the expression

CodeCogsEqn.gif
CodeCogsEqn.gif (1.28 KiB) Viewed 268 times


yields integer results for all integers k>=0 and n>=0

This occurred to me while I was cogitating upon a Mathologer YouTube video.
User avatar
scott1328
THREAD STARTER
 
Name: Some call me... Tim
Posts: 8573
Male

United States (us)
Print view this post

Ads by Google


Re: Challenge

#2  Postby Thommo » Nov 16, 2019 6:10 pm

I didn't come up with anything neat, did you have a nice solution?
User avatar
Thommo
 
Posts: 26617

Print view this post

Re: Challenge

#3  Postby scott1328 » Nov 16, 2019 7:11 pm

no. that’s why I posted the challenge.
User avatar
scott1328
THREAD STARTER
 
Name: Some call me... Tim
Posts: 8573
Male

United States (us)
Print view this post

Re: Challenge

#4  Postby Spearthrower » Nov 16, 2019 7:14 pm

The answer's 5...

... and now I am leaving and never coming back to this thread, so please feel free to call me names. I undoubtedly deserve it.
I'm not an atheist; I just don't believe in gods :- that which I don't belong to isn't a group!
Religion: Mass Stockholm Syndrome

Learn Stuff. Stuff good. https://www.coursera.org/
User avatar
Spearthrower
 
Posts: 25793
Age: 43
Male

Country: Thailand
Print view this post

Re: Challenge

#5  Postby Thommo » Nov 16, 2019 7:18 pm

I might have a longer look.

Not convinced I was onto anything fruitful. At least the k = 0 case is obvious, it's the higher ones that I could see no clear way towards either from properties of combinatorics/pascal's triangle or a simple mathematical induction.
User avatar
Thommo
 
Posts: 26617

Print view this post

Re: Challenge

#6  Postby newolder » Nov 16, 2019 7:31 pm

So far, I have let z = (4k + 1)1/2 and when I let n increase, I'm always left with some integer multiple (2n) of z divided by z because the 1/2 bit always disappears along with the odd powers of z whilst the even powers of z always yield a positive integer (including for all k)...

But I haven't been at all rigorous and haven't even written anything down on paper, yet... :scratch:

edit to correct the function for z :doh:
I am, somehow, less interested in the weight and convolutions of Einstein’s brain than in the near certainty that people of equal talent have lived and died in cotton fields and sweatshops. - Stephen J. Gould
User avatar
newolder
 
Name: Albert Ross
Posts: 6620
Age: 8
Male

Country: Feudal Estate number 9
Print view this post

Re: Challenge

#7  Postby Thommo » Nov 16, 2019 9:00 pm

The first thing I did was let z = (4k+1)1/2 as well. I also took the multilayering out to make the equation look like:
Image

The binomial expansion for that sees the even powers of z cancel and leaves an expression:
Image
With number of terms defined by the highest power being one less than or equal to n.

If you let x = z2 then the square roots go away nicely as well. The only outstanding problem is the 2n-1 in the denominator, and I felt like that must be a clue as to the association with Pascal's triangle, since the lines add up to the powers of 2, and we always have a list of combinations which constitute exactly half a row of Pascal's triangle, but with entries multiplied by various powers of x. Obviously those powers of x always produce binomial expansions with a 1 in them, which we could pull out, giving a full list of half of line n of Pascal's triangle, which is thus divisible by 2n-1, but what's left is looking like a mess.

So I couldn't see how to make an induction step in k from that. I'm not sure if this is even a step in the right direction. :scratch:
User avatar
Thommo
 
Posts: 26617

Print view this post

Ads by Google


Re: Challenge

#8  Postby scott1328 » Nov 19, 2019 1:26 pm

I think I am stuck where you are, Thommo. But you have shown that the expression is always rational.
User avatar
scott1328
THREAD STARTER
 
Name: Some call me... Tim
Posts: 8573
Male

United States (us)
Print view this post

Re: Challenge

#9  Postby Thommo » Nov 19, 2019 5:24 pm

I've not looked much further, but I think I'm stuck. I'm not sure if this is the right approach, but it's somehow tantalising. As you say, the answer is always a dyadic rational, and with the cases for an induction base of either k=0 or n=0 both being trivial it does look like there's something there.

My gut tells me that the induction in n for arbitrary k (and thus avoiding a double induction and the induction in k altogether) is more likely to succeed. There are certain properties of Pascal's triangle (well, of combinations generally, but I find it easier to visualise) that suggest a route for reducing the expressions to a product of the previous steps. You also have a distinct case for the odd and even steps as you only get a new term when n is odd.
User avatar
Thommo
 
Posts: 26617

Print view this post

Re: Challenge

#10  Postby Fallible » Nov 20, 2019 10:16 pm

Yeah I was thinking exactly the same thing. Also, I know pi to 2 places.
Sorry that you think you had it rough in the first world.
You ought to get out of that sooner than later.
Knowledge has turned into a trap; you have to slow down.
Get out of your head and spend less time alone.
User avatar
Fallible
RS Donator
 
Name: Alice Pooper
Posts: 49785
Age: 46
Female

Country: Engerland na na
Canada (ca)
Print view this post

Re: Challenge

#11  Postby Thommo » Nov 20, 2019 11:11 pm

So the identity I think we might want is this one:
Image

Making a couple of definitions:
Image
Image
(I've sorta fudged how many terms are involved in the sums here because I haven't spent much time on it and farting around with latex is a pain)

Means that En+1=En + Fn

Which also looks like a step in the right direction as this is all in terms of combinations at the previous level of n, but now we need an induction on showing F to be divisible by 2n-1 instead of E (since we have already proven E is divisible as required if we prove our induction step). I've used the property that if A = B+C and k divides A and B, then k divides C here, which I think is right, off the top of my head.

I'm wondering if we can't essentially do the same thing again and prove F by defining a G in the same way. :scratch:
User avatar
Thommo
 
Posts: 26617

Print view this post

Re: Challenge

#12  Postby scott1328 » Dec 19, 2019 5:27 pm

Going off on a completely different tack:

Consider the quadratic equation, x^2 - x - k = 0

Solving that equation yields the solutions: x1=(1+Sqrt(4k+1))/2 and x2= (1-Sqrt(4k+1))/2

Also consider that: x^2 = x + k.

Now consider the n=2 case from the original expression which can be rewritten as (x1^2 - x2^2)/Sqrt(4k+1)
The x1^2 term can be substituted with (x1+ k) and the x2^2 term can be substituted with (x2 + k)

Therefore the n=2 case of the expression can be written as
(x1 + k - (x2 + k))/Sqrt(4k+1)
= (x1 - x2)/Sqrt(4k+1)
= (1 + Sqrt(4k+1) - (1 - Sqrt(4k+1))/(2*Sqrt(4k+1))
= (2*Sqrt(4k+1))/(2*Sqrt(4k+1)
= 1

Now consider the n=3 case of the original expression:
x^3 = x*x*2 = x(x+k) = x^2 + xk = (x+k) + xk

Therefore the n=3 case of the expression can be written as
(x1 + k + (x1)k - (x2 + k + (x2)k)/Sqrt(4k+1)
= (x1 - x2 + (x1)k - (x2)k)/Sqrt(4k+1)
= ((x1-x2) + k(x1-x2))/Sqrt(4k+1)
= ((x1-x2)(k+1)/Sqrt(4k+1)
= k+1

Carrying on to the n=4 case:
x^4 = x*x^3 = x((x+k) + xk) = x^2 + kx + kx^2 = (x+k) + kx + kx + k^2 = x + 2kx + k^2

The n=4 case of the expression can be written as
(x1 + 2k(x1) + k^2 - (x2 + 2k(x2) + k^2))/Sqrt(4k+1)
= (x1 - x2 + 2k(x1 - x2))/Sqrt(4k+1)
= 2k+1

Does this boost the argument by induction?
User avatar
scott1328
THREAD STARTER
 
Name: Some call me... Tim
Posts: 8573
Male

United States (us)
Print view this post


Return to Mathematics

Who is online

Users viewing this topic: No registered users and 1 guest