## 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 664 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: 8675  Print view this post

### Re: Challenge

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

Posts: 26985

Print view this post

### Re: Challenge

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

Name: Some call me... Tim
Posts: 8675  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: 27416
Age: 44 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: 26985

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: 7308 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: 26985

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: 8675  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: 26985

Print view this post

### Re: Challenge

Yeah I was thinking exactly the same thing. Also, I know pi to 2 places.
She battled through in every kind of tribulation,
She revelled in adventure and imagination.
She never listened to no hater, liar,
Breaking boundaries and chasing fire.
Oh, my my! Oh my, she flies! Fallible
RS Donator

Name: Alice Pooper
Posts: 51577
Age: 47 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: 26985

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: 8675  Print view this post

### Re: Challenge

I think that it does, but I would have trouble showing that there is sand in the Sahara, so I'm not going to attempt such a proof.

However, I have been having some fun with the problem by endeavoring to compute the polynomials that give the result of the original expression as a function of k for a given n. For example, scott1328 has shown that for n=2 the polynomial is 1, for n=3, the polynomial is k+1, and for n=4 the polynomial is 2k+1.

Again, I have not proven anything, so I can only say that it appears as if the expression always results in an integer, and that the polynomials that I computed give the same result as the original expression for n, k.

Anyway, my method was:
1) Calculate the values of the original expression for each n, k.
2) From the values, derive the polynomial coefficients to use with powers of k for each n.
3) Try to come up with a formula for the coefficients for all n, k.
4) Try to find a look-up table to make it easier - for hand computations, at least. These are the polynomial coefficients mentioned in 2).

So here are the results. The formula I arrived at is (don't worry, it gets easier): rs_2020_02_09_expr_latex.JPG (17.31 KiB) Viewed 327 times

For example, for n=4: rs_2020_02_09_expr_n_eq_4_latex.JPG (12.55 KiB) Viewed 327 times

as previously given.

But let's just go to a look-up table instead of relying on the formula. A look-up table may be found at OEIS A102426 by scrolling down to the EXAMPLE section. The first few polynomials are given in terms of x, but in order to calculate the expression result, we just replace x with k. a102426_ex.JPG (25.45 KiB) Viewed 327 times
but i do have a signature
i have no avatar

Posts: 1185 Country: USA Print view this post

### Re: Challenge

Well, crud, I guess only 3 attachments may be uploaded at a time (at least inline).

Continuing from above:

As an example, if we want to calculate the result for n=10, k=7, we look at the "10:" row and we calculate: rs_2020_02_09_expr_n_10_k_7_latex.JPG (13.02 KiB) Viewed 327 times

which agrees with a direct calculation from the original expression.

Finally, one last thing. Similar to OEIS A102426, is OEIS A030528 which has some leading zeros such that in the EXAMPLE section of that sequence, the rows of Pascal's Triangle (starting from row 1) show up as columns in the table. Note that to get the coefficients for n from this table, we need to choose row [n - 1]. a030528.JPG (24.85 KiB) Viewed 327 times
but i do have a signature
i have no avatar

Posts: 1185 Country: USA Print view this post