## Challenge

(probably simple, but I found it interesting)

Discuss the language of the universe.

### Challenge

Show that the expression 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. scott1328

Name: Some call me... Tim
Posts: 8573  Print view this post

### Re: Challenge

I didn't come up with anything neat, did you have a nice solution? Thommo

Posts: 26617

Print view this post

### Re: Challenge

no. that’s why I posted the challenge. scott1328

Name: Some call me... Tim
Posts: 8573  Print view this post

### Re: Challenge

... 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/ Spearthrower

Posts: 25793
Age: 43 Country: Thailand
Print view this post

### Re: Challenge

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. Thommo

Posts: 26617

Print view this post

### Re: Challenge

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... edit to correct the function for z 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 newolder

Name: Albert Ross
Posts: 6620
Age: 8 Country: Feudal Estate number 9
Print view this post

### Re: Challenge

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: The binomial expansion for that sees the even powers of z cancel and leaves an expression: 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.  Thommo

Posts: 26617

Print view this post

### Re: Challenge

I think I am stuck where you are, Thommo. But you have shown that the expression is always rational. scott1328

Name: Some call me... Tim
Posts: 8573  Print view this post

### Re: Challenge

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. Thommo

Posts: 26617

Print view this post

### Re: Challenge

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. Fallible
RS Donator

Name: Alice Pooper
Posts: 49785
Age: 46 Country: Engerland na na Print view this post

### Re: Challenge

So the identity I think we might want is this one: Making a couple of definitions:  (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.  Thommo

Posts: 26617

Print view this post

### Re: Challenge

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? scott1328

Name: Some call me... Tim
Posts: 8573  Print view this post