Scribd
Upload
5 views2 pages

Solution 249

The document presents a proof that any polynomial of degree d can be expressed as a linear combination of specific polynomials Q_l(x). It demonstrates this using induction and concludes that the sum of the polynomial evaluated at k, weighted by binomial coefficients, equals the leading coefficient c multiplied by d factorial. The proof verifies the relationship through algebraic manipulation and properties of polynomials.

Uploaded by

aayooshkumar2003
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views2 pages

Solution 249

The document presents a proof that any polynomial of degree d can be expressed as a linear combination of specific polynomials Q_l(x). It demonstrates this using induction and concludes that the sum of the polynomial evaluated at k, weighted by binomial coefficients, equals the leading coefficient c multiplied by d factorial. The proof verifies the relationship through algebraic manipulation and properties of polynomials.

Uploaded by

aayooshkumar2003
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

1

PSI

(𝑄) Show that


𝑑
𝑑
∑(−1)𝑑−𝑘 ( ) 𝑃(𝑘) = 𝑐. 𝑑!
𝑘
𝑘=0

where 𝑐 is the leading coefficient of polynomial 𝑃(𝑥) of degree 𝑑.

Solution:
We define, 𝑄𝑙 (𝑥) = 𝑥(𝑥 − 1)(𝑥 − 2) … (𝑥 − 𝑙 + 1), and 𝑄0 (𝑥) = 1 ∀ 𝑥 ∈ ℝ,
Claim: Every polynomial 𝑅(𝑥) of degree 𝑛 can be represented as a linear combination of 𝑄𝑙 (𝑥), 0 ≤
𝑙≤𝑛
𝑅(𝑥) = 𝑐𝑛 𝑄𝑛 (𝑥) + 𝑐𝑛−1 𝑄𝑛−1 (𝑥) + 𝑐𝑛−2 𝑄𝑛−2 (𝑥) + ⋯ + 𝑐0 𝑄0 (𝑥) , 𝑐𝑖 ∈ ℝ ∀ 𝑖 = {1,2, . . , 𝑛}

Proof: For the base case 𝑛 = 0 we have 𝑅(𝑥) = 𝑐0 which is any constant polynomial. For 𝑛 = 1, we have
𝑅(𝑥) = 𝑐1 𝑥 + 𝑐0 , which represents all linear polynomials.
Now, assume that any polynomial of degree 𝑛 − 1 can be written as a linear combination of 𝑄𝑚 (𝑥),
where 0 ≤ 𝑚 ≤ 𝑛 − 1. Then we have,
𝑆(𝑥) = 𝑐𝑛−1 𝑄𝑛−1 (𝑥) + 𝑐𝑛−1 𝑄𝑛−1 (𝑥) + 𝑐𝑛−2 𝑄𝑛−2 (𝑥) + ⋯ + 𝑐0 𝑄0 (𝑥), 𝑐𝑗 ∈ ℝ ∀ 𝑗 = {1,2, . . , 𝑛 − 1}
For degree 𝑛 we need,
𝑅(𝑥) = 𝑐𝑛 𝑄𝑛 (𝑥) + 𝑐𝑛−1 𝑄𝑛−1 (𝑥) + 𝑐𝑛−2 𝑄𝑛−2 (𝑥) + ⋯ + 𝑐0 𝑄0 (𝑥) , 𝑐𝑖 ∈ ℝ ∀ 𝑖 = {1,2, . . , 𝑛}
𝑅(𝑥) = 𝑐𝑛 𝑄𝑛 (𝑥) + 𝑆(𝑥)
From our inductive step, since 𝑆(𝑥) is any polynomial of degree 𝑛 − 1, therefore 𝑅(𝑥) is any polynomial of
degree 𝑛. Thus, by induction, Every polynomial 𝑅(𝑥) of degree 𝑛 can be represented as a linear
combination of 𝑄𝑙 (𝑥), 0 ≤ 𝑙 ≤ 𝑛.
Now, 𝑃(𝑥) is a polynomial of degree 𝑑, we can write it as
𝑑

𝑃(𝑥) = ∑ 𝑎𝑟 𝑄𝑟 (𝑥)
𝑟=0

Now, our original sum,


𝑑 𝑑 𝑘 𝑑 𝑑
𝑑−𝑘
𝑑 𝑑 𝑑
∑(−1) ( ) 𝑃(𝑘) = ∑(−1)𝑑−𝑘 ( ) ∑ 𝑎𝑟 𝑄𝑟 (𝑘) = ∑ 𝑎𝑟 ∑(−1)𝑑−𝑘 ( ) 𝑄𝑟 (𝑘)
𝑘 𝑘 𝑘
𝑘−0 𝑘=0 𝑟=0 𝑟=0 𝑘=𝑟

Observe the term,


𝑑 𝑑! 𝑘! 𝑑! (𝑑 − 𝑟)! 𝑑−𝑟
( ) 𝑄𝑟 (𝑘) = . = . = 𝑄𝑟 (𝑑) ( )
𝑘 𝑘! (𝑑 − 𝑘)! (𝑘 − 𝑟)! (𝑑 − 𝑟)! (𝑘 − 𝑟)! (𝑑 − 𝑘)! 𝑑−𝑘
So, our sum becomes,
𝑑 𝑑
𝑑−𝑟
(−1)𝑑 ∑ 𝑎𝑟 𝑄𝑟 (𝑑) ∑(−1)𝑘 ( )
𝑘−𝑟
𝑟=0 𝑘=𝑟
2
PSI
𝑑 𝑑−𝑟
𝑑−𝑟
(−1)𝑑 ∑(−1) 𝑎𝑟 𝑄𝑟 (𝑑) ∑(−1)𝑝 (
𝑟
)=
𝑝
𝑟=0 𝑝=0

Observe that for all 𝑟 < 𝑑, we have


𝑑−𝑟
𝑑−𝑟
∑(−1)𝑝 ( ) =0
𝑝
𝑝=0

For, 𝑟 = 𝑑 we have,
0
0
∑(−1)𝑝 ( ) = 1
𝑝
𝑝=0

Therefore,
𝑑 𝑑−𝑟
𝑑−𝑟
(−1)𝑑 ∑(−1)𝑟 𝑎𝑟 𝑄𝑟 (𝑑) ∑(−1)𝑝 ( ) = (−1)2𝑑 𝑎𝑑 𝑄𝑑 (𝑑) = 𝑎𝑑 . 𝑑. (𝑑 − 1) … 1 = 𝑎𝑑 . 𝑑!
𝑝
𝑟=0 𝑝=0

Here, 𝑎𝑑 is the leading coefficient. According to question, 𝑎𝑑 = 𝑐. Thus, we have


𝑑
𝑑
∑(−1)𝑑−𝑘 ( ) 𝑃(𝑘) = 𝑐. 𝑑!
𝑘
𝑘=0

You might also like