What Is Lockwood's Identity and How Does It Relate to Pascal's Triangle?

[robimaru]

i am working on my expository research about integer sequences and their relationship with the pascal's triangle using the Lockwood's identity.
but unfortunately i can't provide a complete proof for the said identity. please help me. I've been working on it for months but still i can't do the proof.
the equation is too long so maybe it would be okay if I'd just give the link?
here it is:

http://ms.appliedprobability.org/data/files/feature articles/43-3-6.pdf

any help will be highly appreciated.

 

[Stephen Tashi]

I'd hate to have to do that proof, but I don't mind "discussing" it.

Your request is for an inductive proof of the pattern suggested by the equations:
$$x^1 + y^1 = (x+y)^1$$
$$x^2 + y^2 = (x+y)^2 - 2 (xy)$$
$$x^3 + y^3 = (x+y)^3 - 3(xy)(x+y)$$
$$x^4 + y^4 = (x+4)^4 - 4(xy)(x+y)^2 + 2(xy)^2$$
$$x^5 + y^5 = (x+y)^5 - 5(xy)(x+y)^3 + 5(xy)^2(x+y)$$

Essentially it asks to prove the general formula for expanding $$x^n + y^n$$ in a (finite) power series in the variables $\theta = x + y$ and $\alpha = xy$.

The article says this is done by strong induction and messy algebra.

I notice that if you multiply one of the equations on both sides by $(x+y)$ then it's right hand side has some resemblance to the right hand side of the next equation in the series. The left hand side becomes something that is expressible in terms of the previous equations. For example, left hand side of $x^4 + y^4$ becomes:

$$(x+ y) (x^4 + y^4) = x^5 + y ^5 + yx^4 + xy^4 = x^5 + y^5 + (xy)(x^3 + y^3)$$

So if you subtract the term $(xy)(x^3 + y^3)$ from both sides and then employ the equation for $x^3 + y^3$, you should establish the equation for $x^5 + y^5$.

 

[robimaru]

thank you sir!
that is the middle term of the expansion.
I'm almost done with the proof. i did the induction and it came up well..
my only problem now is on how to evaluate the first term inside the summation part.
is there a property of summation that says that when the upper limit is less than the lower limit, its value will be zero?

 

[dodo]

Sorry to meddle but, just as a side comment, wouldn't this Lockwood's identity be telling a bunch of relations among the entries in Pascal's triangle? For example, expand the binomials (x+y)^2 and (x+y)^4 to obtain$$x^2 + y^2 = (x+y)^2 - {2 \choose 1}xy$$and$$\begin{align*}x^4 + y^4 &= (x+y)^4 - {4 \choose 1}x^3 y - {4 \choose 2}x^2 y^2 - {4 \choose 3}x y^3 \\<br /> &= (x+y)^4 - {4 \choose 1}xy(x^2+y^2) - {4 \choose 2}(xy)^2\end{align*}$$and, after substituting the first into the second,$$\begin{align*}x^4 + y^4 &= (x+y)^4 - {4 \choose 1}xy \left((x+y)^2 - {2 \choose 1}xy \right) - {4 \choose 2}(xy)^2 \\<br /> &= (x+y)^4 - {4 \choose 1}xy (x+y)^2 + \left( {4 \choose 1}{2 \choose 1} - {4 \choose 2}\right) (xy)^2\end{align*}$$whereas Lockwood's identity would give you$$x^4 + y^4 = (x+y)^4 - \left( {3 \choose 1} + {2 \choose 0} \right) xy (x+y)^2 + \left( {2 \choose 2} + {1 \choose 1} \right)(xy)^2$$so$$\begin{align*} {4 \choose 1} &= {3 \choose 1} + {2 \choose 0} \\ {4 \choose 1}{2 \choose 1} - {4 \choose 2} &= {2 \choose 2} + {1 \choose 1} \end{align*}$$and it doesn't appear like a coincidence; in fact it only gets more complicated with higher powers.

 

[Stephen Tashi]

is there a property of summation that says that when the upper limit is less than the lower limit, its value will be zero?

That is a common convention in summation notation, but if you are writing a proof, you can't justify a step because of a notational convention. If the indicated computation implies that there are no terms of a certain type to sum, you can point that out in words.

 

[Stephen Tashi]

wouldn't this Lockwood's identity be telling a bunch of relations among the entries in Pascal's triangle?

My guess is yes, since the article by Lockwood that is referenced in the link has a title mentioning Pascal's triangle. But I haven't read Lockwood's article.

 

[robimaru]

aw the proof that we made seems wrong.
i'm afraid that we may fail the subject if we don't have the proof. i tried to contact the author of the article but he didn't respond.

using induction, x^n+ y^n=(x+y)^n+ ∑_(k=0)^⌊n/2⌋▒〖(-1)〗^k [((n-k)¦k) + ((n-k-1)¦(k-1)) ] (xy)^k (x+y)^(n-2k)
how can i prove that this holds for n+1.

having (x+y) be multiplied on both sides will give x^(n+1) + y^(n+1)
but it also produces a middle term x^(n+1)y+xy^(n+1).

 

[Stephen Tashi]

but it also produces a middle term x^(n+1)y+xy^(n+1).

Of course it does and
$x^{n+1} y + x y^{n+1} = (xy) ( x^n + y^n)$, as illustrated by my example for the case n = 4.

 

[robimaru]

yes but what am i going to do in the proof?

 

[Stephen Tashi]

I suggest you look at the example and perhaps do another one of your own. Then try to write the example symbolically using summation notation. How exactly did you get into the situation of having to prove this result if you don't have much experience in writing proofs by induction?