Difference between revisions of "User talk:PaoloMartini"
Jump to navigation
Jump to search
PaoloMartini (talk | contribs) |
PaoloMartini (talk | contribs) |
||
(3 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
⚫ | |||
− | Show that if <math>p(x)</math> is a polynomial of degree <math>n</math>, then <math>p(x - 1)</math> is a polynomial of the same degree. |
||
⚫ | |||
− | Definition of polynomial. |
||
− | + | <math>p(x-1) = a_n (x-1)^n + \sum_{i=0}^{n-1} a_i (x-1)^i </math> |
|
⚫ | |||
− | Binomial theorem. |
||
− | + | <math>p(x-1) = a_n \sum_{k=0}^n {n \choose k} x^{n-k} (-1)^k + \sum_{i=0}^{n-1} a_i (x-1)^i </math> |
|
+ | <math>p(x-1) = a_n x^n + a_n \sum_{k=1}^n {n \choose k} x^{n-k} (-1)^k + \sum_{i=0}^{n-1} a_i (x-1)^i </math> |
||
− | Special case. |
||
+ | <haskell> |
||
⚫ | |||
+ | {-# OPTIONS_GHC -fglasgow-exts #-} |
||
+ | module Polynomial where |
||
+ | import Test.QuickCheck |
||
− | Binomial coefficient simmetry. |
||
+ | -- *f*actorial |
||
− | :<math>{n \choose k} = {n \choose n-k} </math> |
||
+ | f :: Integer -> Integer |
||
+ | f n = product [1..n] |
||
+ | -- *c*hoose -- binomial coefficient |
||
− | Hence: |
||
+ | c :: Integer -> Integer -> Integer |
||
+ | n `c` k = f n `div` (f k * f (n-k)) |
||
+ | -- *p*olynomial |
||
⚫ | |||
+ | p, q :: [Integer] -> Integer -> Integer |
||
+ | p a x = sum [(a!!fromIntegral i)*(x^i) | i <- [0..n]] where n = length a - 1 |
||
− | + | q a x = ((a!!n) * ((x+1)^n)) |
|
+ | + ((a!!n) * sum [(fromIntegral n `c` fromIntegral k)*((x+1)^(n-k))*((-1)^k) | k <- [1..n]]) |
||
− | = \sum_{i=0}^n \left[ a_i \left( \sum_{k=0}^n {n \choose k} x^k (-1)^k \right) \right] |
||
+ | + sum [(a!!fromIntegral i)*(x^i) | i <- [0..n-1]] where n = length a - 1 |
||
− | = \sum_{i=0}^n \sum_{k=0}^i a_i {n \choose k} x^k (-1)^k |
||
⚫ | |||
+ | -- *t*est |
||
− | QED. |
||
+ | t = quickCheck $ \(x::Integer) (xs::[Integer]) -> |
||
− | |||
+ | not (null xs) && last xs /= 0 ==> p xs x == q xs x |
||
− | ---- |
||
+ | </haskell> |
Latest revision as of 20:41, 15 September 2006
{-# OPTIONS_GHC -fglasgow-exts #-}
module Polynomial where
import Test.QuickCheck
-- *f*actorial
f :: Integer -> Integer
f n = product [1..n]
-- *c*hoose -- binomial coefficient
c :: Integer -> Integer -> Integer
n `c` k = f n `div` (f k * f (n-k))
-- *p*olynomial
p, q :: [Integer] -> Integer -> Integer
p a x = sum [(a!!fromIntegral i)*(x^i) | i <- [0..n]] where n = length a - 1
q a x = ((a!!n) * ((x+1)^n))
+ ((a!!n) * sum [(fromIntegral n `c` fromIntegral k)*((x+1)^(n-k))*((-1)^k) | k <- [1..n]])
+ sum [(a!!fromIntegral i)*(x^i) | i <- [0..n-1]] where n = length a - 1
-- *t*est
t = quickCheck $ \(x::Integer) (xs::[Integer]) ->
not (null xs) && last xs /= 0 ==> p xs x == q xs x