Show that the expression



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

This occurred to me while I was cogitating upon a Mathologer YouTube video.

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

no. that’s why I posted the challenge.

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

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

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.

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

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.

Yeah I was thinking exactly the same thing. Also, I know pi to 2 places.

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.

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?

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):


For example, for n=4:

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.

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:


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

I watched this video today and it reminded me of this challenge. From about 33:30 to about 35:00 is of particular interest, but obviously he uses material that was presented earlier in the video.

Basically, the case for k=1 corresponds to a quadratic difference equation related to the Fibonacci sequence and it is Binet's formula. I ran some simple calculations and it appears that for k in general, the related sequence is a sequence starting with a(0), a(1) = 0,1 with subsequent values given by a(n) = a(n-2)*k + a(n-1), n >= 2 .

So for k=3 the related sequence calculates to 0,1,1,4,7,19,40,97...

The link provided above gives a couple of proofs of Binet's formula, which I assume could be used by someone (not me) to provide a solution to the challenge, maybe via induction on k ? If so, obviously, the numbers are integers for all k,n .