Showing that one polynomial divides another

[Mr Davis 97]

Homework Statement

Show that ##\displaystyle \sum_{i=0}^{100} {100\choose i}{200-i\choose 198-i}x^i## is divisible ##(x+1)^{98}##.

Homework Equations

The Attempt at a Solution

I am pretty stumped, but I have a few general. I think that the the binomial theorem will be involved. That is, I think we will have to use the fact that ##\displaystyle (x+1)^{98} = \sum_{i=0}^{98} {98\choose i}x^i##. Also, I think that we might have to use a combinatorial identity to simplify the first expression, but I am not sure... Another idea of mine was to try to show that the remainder must be zero, but then I see that this would involved a polynomial of degree 97 or less, which doesn't help very much with simplifying the problem... I think I just need to be nudged in the right direction.

 

[andrewkirk]

I think we will have to use the fact that ##\displaystyle (x+1)^{98} = \sum_{i=0}^{98} {98\choose i}x^i##.

Why not just use that fact directly in an explicit binomial division? The quotient will be of order two, ie ##ax^2+bx+c##, so only three numbers need to be found, and the division will only have three stages.

In fact we can immediately observe that ##a=\pmatrix{100\\100}\pmatrix{100\\98} = 100\times 99/2 = 4,950##.

So the first step will be to write out a formula for ##P(x) - ax^2\times (x+1)^{98}##.

 

[Mr Davis 97]

Why not just use that fact directly in an explicit binomial division? The quotient will be of order two, ie ##ax^2+bx+c##, so only three numbers need to be found, and the division will only have three stages.

In fact we can immediately observe that ##a=\pmatrix{100\\100}\pmatrix{100\\98} = 100\times 99/2 = 4,950##.

So the first step will be to write out a formula for ##P(x) - ax^2\times (x+1)^{98}##.

I have a few questions. Is it because we are dividing a 100th degree polynomial by a 98th degree polynomial that the quotient must be a 2nd degree polynomial? Also, why are we trying to find the coefficients of this quotient? What about the remainder, which we might want to try to show to be zero? Also, what is ##P (x)##?

 

[andrewkirk]

##P(x)## is the polynomial given in the OP. The answer to the first question is Yes, as the degree of the product of two polynomials is the sum of their degrees. The process for finding the coefficients is just the process of performing the division. The coefficients ##a,b,c## are obtained from the 1st, 2nd and 3rd stages of the division respectively. And calculating the remainder - in this case hoping it is zero - is an integral part of concluding the division. If it turns out to be zero as we expect, we will have proven the claim, and as an added bonus, we will know the quotient.

 

[Mr Davis 97]

##P(x)## is the polynomial given in the OP. The answer to the first question is Yes, as the degree of the product of two polynomials is the sum of their degrees. The process for finding the coefficients is just the process of performing the division. The coefficients ##a,b,c## are obtained from the 1st, 2nd and 3rd stages of the division respectively. And calculating the remainder - in this case hoping it is zero - is an integral part of concluding the division. If it turns out to be zero as we expect, we will have proven the claim, and as an added bonus, we will know the quotient.

I found that ##P(x) - ax^2 (x+1)^{98} = [{100\choose 99}{101\choose 99} - a{98\choose 97}]x^{99} + [{100\choose 98}{102\choose 100} - a{98\choose 96}]x^{98} + \cdots ##. Does this show that ##b = [{100\choose 99}{101\choose 99} - a{98\choose 97}] = 19900##?

 

[andrewkirk]

Yes, if the calculation was correct, that will be the value of ##b##.

 

[StoneTemplePython]

Homework Statement

Show that ##\displaystyle \sum_{i=0}^{100} {100\choose i}{200-i\choose 198-i}x^i## is divisible ##(x+1)^{98}##.

an alternative approach:

working with a monic polynomial is typically easier -- i.e. leading coefficient of one. So divide everything in your original polynomial by ##\alpha =\binom{100}{100} \binom{200-100}{100-98} =\binom{100}{2}##

the problem reduces to showing

##\frac{1}{\alpha} \displaystyle \sum_{i=0}^{100} {100\choose i}{200-i\choose 198-i}x^i =\Big(x^2 + bx + c\Big)\big(x+1\big)^{98}= \Big(\big(x-\lambda_{1} \big)\big(x-\lambda_{2} \big)\Big) \big(x - (-1)\big)^{98} = \big(x-\lambda_{1} \big)\big(x-\lambda_{2} \big)\big(x - \lambda_3\big)^{98} ##

##\lambda_1## and ##\lambda_2## should be easy to uncover here (hint: think trace and determinant) -- or if you prefer: ##b## and ##c##.

Then direct multiplication gives the proof / verifies the claim.
- - - - -

It may be possible to skip the direct multiplication and verify the elementary symmetric sums line up -- given all the roots of ##(-1)## and the combinatoric structure, I have a suspicion this is what was intended.

 

[andrewkirk]

Another approach that occurs to me is that, if ##(x+1)^{98}## divides the polynomial ##P(x)## then ##-1## is a root of ##P(x)## with multiplicity 98, which means that ##P^{(k)}(-1)=0## for ##0\le k\le 97##, where the superscript ##(k)## indicates number of times the polynomial has been differentiated.

We go from
$$P(x)=\sum_{i=0}^{100}\pmatrix{100\\i}\pmatrix{200-i\\198-i}x^i$$
to
$$P^{(k)}(x) = \sum_{i=k}^{100}
\pmatrix{100\\i}\pmatrix{200-i\\198-i}\frac{i!}{(i-k)!}
x^{i-k}$$
so the problem requires us to prove that, for ##k## any integer between 0 and 97 inclusive:
$$
\sum_{i=k}^{100}
\pmatrix{100\\i}\pmatrix{200-i\\198-i}\frac{i!}{(i-k)!}
(-1)^{i-k}
=0$$

 

[Ray Vickson]

Homework Statement

Show that ##\displaystyle \sum_{i=0}^{100} {100\choose i}{200-i\choose 198-i}x^i## is divisible ##(x+1)^{98}##.

Homework Equations

The Attempt at a Solution

I am pretty stumped, but I have a few general. I think that the the binomial theorem will be involved. That is, I think we will have to use the fact that ##\displaystyle (x+1)^{98} = \sum_{i=0}^{98} {98\choose i}x^i##. Also, I think that we might have to use a combinatorial identity to simplify the first expression, but I am not sure... Another idea of mine was to try to show that the remainder must be zero, but then I see that this would involved a polynomial of degree 97 or less, which doesn't help very much with simplifying the problem... I think I just need to be nudged in the right direction.

Yet another approach is to note that ##{200-i \choose 198-i}## is easy to write out in detail---it is quadratic in ##i##. So, you get a sum of the form
$$\sum_{i=0}^{100} {100 \choose i} (a + b i + c i(i-1)) x^i ,$$
and since ##i x^i = x (d/dx) x^i, \: i(i-1) x^i = x^2 (d/dx)^2 x^i, ## we have that your sum has the form
$$\text{sum} = (a + b x D + c x^2 D^2) (1+x)^{100}, $$
where ##D = d/dx.##