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 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.
User avatar
scott1328
THREAD STARTER
 
Name: Some call me... Tim
Posts: 8675
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: 26985

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: 8675
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: 27416
Age: 44
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: 26985

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

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

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.
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!
User avatar
Fallible
RS Donator
 
Name: Alice Pooper
Posts: 51577
Age: 47
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: 26985

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

United States (us)
Print view this post

Re: Challenge

#13  Postby i have no avatar » Feb 10, 2020 1:25 am

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
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
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
a102426_ex.JPG (25.45 KiB) Viewed 327 times
but i do have a signature
i have no avatar
 
Posts: 1185
Male

Country: USA
United States (us)
Print view this post

Re: Challenge

#14  Postby i have no avatar » Feb 10, 2020 1:26 am

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
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
a030528.JPG (24.85 KiB) Viewed 327 times
but i do have a signature
i have no avatar
 
Posts: 1185
Male

Country: USA
United States (us)
Print view this post


Return to Mathematics

Who is online

Users viewing this topic: No registered users and 1 guest