Proving Chebyshev Polynomial Closed Formulas for n = 0, n = 1, and n = 2

Proving Chebyshev Polynomial Closed Formulas for n = 0, n = 1, and n = 2

Chebyshev Polynomials of the First Kind

Recurrence Definition:

T_0(x) = 1

T_1(x) = x

T_n+1(x) = 2 * x * T_n(x) - T_n-1(x)

Closed Definition:

T_n(x) = 1/2 * [ (x - √(x^2 - 1))^n + (x + √(x^2 - 1))^n ]

Let: w = √(x^2 - 1)

T_n(x) = 1/2 * [ (x - w)^n + (x + w)^n ]

n = 0

T_0(x) 

= 1/2 * [ (x - w)^0 + (x + w)^0 ]

= 1/2 * [ 1 + 1 ] 

= 1

n = 1

T_1(x)

= 1/2 * [ (x - w)^1 + (x + w)^1 ]

= 1/2 * [ x - w + x + w ]

= 1/2 * [ 2 * x]

= x

n = 2

T_2(x)

= 1/2 * [ (x - w)^2 + (x + w)^2 ]

= 1/2 * [ x^2 - 2*w + w^2 + x^2 + 2*w^2 + w^2 ]

= 1/2 * [ 2 * x^2 + 2 * w^2 ]

= x^2 + x^2 - 1

= 2 * x^2 - 1

Chebyshev Polynomials of the Second Kind

Recurrence Definition:

U_0(x) = 1

U_1(x) = 2 * x

U_n+1(x) = 2 * x * U_n(x) - U_n-1(x)

Closed Definition:

U_n(x) = [ (x + √(x^2 - 1))^(n + 1) - (x - √(x^2 - 1))^(n + 1) ] ÷ [ 2 * √(x^2 - 1) ]

Let: w = √(x^2 - 1)

U_n(x) = [ (x + w)^(n + 1) - (x - w)^(n + 1) ] ÷ [ 2 * w ]

n = 0

U_0(x)

= [ (x + w)^(1) - (x - w)^(1) ] ÷ [ 2 * w ]

= [ x + w - x + w ] ÷ (2 * w)

= (2 * w) ÷ (2 * w)

= 1

n = 1

U_1(x)

= [ (x + w)^(2) - (x - w)^(2) ] ÷ [ 2 * w ]

= [ (x^2 + 2 * x * w + w^2) - (x^2 - 2 * x * w + w^2) ] ÷ (2 * w)

= [ 4 * x * w ] ÷ (2 * w)

= 2 * x

n = 2

U_2(x)

= [ (x + w)^(3) - (x - w)^(3) ] ÷ [ 2 * w ]

= [ x^3 + 3*x^2*w + 3*x*w^2 + w^3 - (x^3 - 3*x^2*w + 3*x*w^2 - w^3)] ÷ [ 2*w ]

= [ x^3 + 3*x^2*w + 3*x*w^2 + w^3 - x^3 + 3*x^2*w - 3*x*w^2 + w^3] ÷ [ 2*w ]

= [ 6*x^2*w + 2*w^3 ] ÷ [ 2*w ]

= [ 6*x*√(x^2 - 1) + 2*(x^2 - 1)^(3/2) ] ÷ [ 2*√(x^2 - 1)  ]

= [ 6*x*√(x^2 - 1) + 2*(x^2 - 1)*√(x^2- 1) ] ÷ [ 2*√(x^2 - 1)  ]

= [ 6*x*√(x^2 - 1) + 2*(x^2 - 1)*√(x^2- 1) ] ÷ [ 2*√(x^2 - 1)  ]

= [ 6*x*√(x^2 - 1) + (2*x^2 - 2)*√(x^2- 1) ] ÷ [ 2*√(x^2 - 1)  ]

= [ (8*x - 2)*√(x^2 - 1) ] ÷ [ 2*√(x^2 - 1)  ]

= 4*x^2 - 1

Good that the closed formulas hold up, at least for n = 0, 1, 2.   The closed formulas would be good if you don't want to use recurrence relations.  

Sources:

"Chebyshev polynomials"  Wikipedia.   https://en.wikipedia.org/wiki/Chebyshev_polynomials  Last Updated July 20, 2022.  Last Accessed June 21, 2022

Oldman, Keith, Jan Myland, & Jerome Spainer  An Atlas of Functions: with Equator, the Atlas Function Calculator  2nd Edition   Springer:  New York, NY.  2009  ISBN 978-0-387-48806-6

Eddie

All original content copyright, © 2011-2022.  Edward Shore.   Unauthorized use and/or unauthorized distribution for commercial purposes without express and written permission from the author is strictly prohibited.  This blog entry may be distributed for noncommercial purposes, provided that full credit is given to the author. 

Lines with Opposite-Signed Slopes

 Lines with Opposite-Signed Slopes

Take two lines, each with opposite signed slopes.  One slope has a positive slope, the other has a negative slope.   In general, the pair of lines will always intersect at one point.

Define two lines as such:

y = m1 ∙ x  + b1,  where m is the slope and b is the y-intercept.   

y = m2 ∙ x + b2

Assume that m1 and m2 are not zero, and m1 > 0 and m2 < 0.

If m2 < 0, -|m2| < 0  (see Aside) 

and as a result, m2 = -|m2|   

Also,  since m1 > 0, |m1| > 0, and m1 = |m1|.   

Equating both lines and solving for x:   

m1 ∙ x + b1 = m2 ∙ x + b2

|m1| ∙ x + b1 = -|m2| ∙ x + b2

|m1| ∙ x + |m2| ∙ x = b2 - b1

x = (b2 - b1) ÷ (|m1| + |m2|)

Since m1 and m2 are not zero, the above solution is defined.   

QED

- - - - - - - - - --  - 

Aside:    If x < 0, then  -|x| < 0  

Assume x is not zero. 

By definition, the absolute value of x, denoted as |x|, is the defined as the distance x is from 0 and is always positive. 

Then:

|x| > 0 

Multiply both sides by -1:

-|x| < 0

- - - - - - - - - --  - 

Eddie

All original content copyright, © 2011-2022.  Edward Shore.   Unauthorized use and/or unauthorized distribution for commercial purposes without express and written permission from the author is strictly prohibited.  This blog entry may be distributed for noncommercial purposes, provided that full credit is given to the author. 

Σ(1 / (a^n)) from n=1 to m

 Σ(1 / (a^n)) from n=1 to m

This blog entry covers the sum of the series:

Σ[1 / (a^n), n=1 to m] with n and m positive integers

Specific Cases:  a = 2 and a = 3

When a = 2:

m = 1:   1/2

m = 2:   1/2 + 1/4  = (2 + 1)/4 = 3/4

m = 3:   1/2 + 1/4 + 1/8 = (4 + 2 + 1)/8 = 7/8

m = 4:   1/2 + 1/4 + 1/8 + 1/16 = (8 + 4 + 2 + 1)/16 = 15/16

Going from the pattern,

Σ[1 / (2^n), n=1 to m] = 1/(2^m) * Σ[(2^n), n=0 to m-1] = (2^m - 1) / 2^m 

When a = 3:

m = 1:  1/3

m = 2:  1/3 + 1/9  = (3 + 1)/9 = 4/9

m = 3:  1/3 + 1/9 + 1/27 = (9 + 3 + 1)/27 = 13/27

m = 4:  1/3 + 1/9 + 1/27 + 1/81 = (27 + 9 + 3 + 1)/81 = 40/81

Going from the pattern,

Σ[1 / (3^n), n=1 to m] = 1/(3^m) * Σ[(3^n), n=0 to m-1]

Finding the General Formula and Proof

Let's presume that, for any a:

Σ[1 / (a^n), n=1 to m-1] = 1/(a^(m-1) * Σ[(a^n), n=0 to m-2]

Let's add 1/(a^m) to the series:  

Σ[1 / (a^n), n=1 to m-1]  + 1/(a^m)

= (1 + a + a^2 + ... + a^(m-3) + a^(m-2)) / (a^(m-1)) + 1 / (a^m)

= (a * (1 + a + a^2 + ... + a^(m-3) + a^(m-2)) + 1) / (a^m)

= (a + a^2 + a^3 + ... + a^(m-2) + a^(m-1) + 1) / (a^m)

= 1/(a^(m)) * Σ[(a^n), n=0 to m-1]

The general formula is now: 

Σ[1 / (a^n), n=1 to m] = 1/(a^(m)) * Σ[(a^n), n=0 to m-1]

Until next time,

Eddie

All original content copyright, © 2011-2021.  Edward Shore.   Unauthorized use and/or unauthorized distribution for commercial purposes without express and written permission from the author is strictly prohibited.  This blog entry may be distributed for noncommercial purposes, provided that full credit is given to the author. 

The Sum of a Constant

The Sum of a Constant

Introduction

What is the sum of the series:

∑ a from x= 0 to n   (a is a real or complex constant, n is a positive integer)

I may not be what you think.   Take a close look at the limits:  lower limit of 0, upper limit of n.   Assume the increment of x is 1. 

The sum of the series is (n + 1) * a.

Proof

Base case.   Let n = 1.  Then:

∑ a from x = 0 to 1

=  a + a   

= 2 * a

= (1 + 1) * a

The value a is added for the x=0 term.   The value a is added for the x=1 term.

Induction.   Assume for a positive integer k,  the series holds.  Then for the sum from x = 0 to x = k + 1:

∑ a from x = 0 to k+1

= ( ∑ a from x = 0 to k ) + ( ∑ a from x = k+1 to k+1 )

= (k + 1) * a + a

= k * a + a + a

= k * a + 2 * a

= (k + 2) * a    QED

Examples


Example 1:

∑ a from x = 0 to 2

= a + a + a

= 3 * a


Example 2:

∑ 6 from x = 0 to 11

= (11 + 1) * 6

= 12 * 6

= 72


Eddie

All original content copyright, © 2011-2020.  Edward Shore.   Unauthorized use and/or unauthorized distribution for commercial purposes without express and written permission from the author is strictly prohibited.  This blog entry may be distributed for noncommercial purposes, provided that full credit is given to the author.

Combinatorics Derivations

Combinatorics Derivations

The definition of the combination function is:

C(n, r) = n! / (r! *  (n – r)!)

Today I am going to mathematically verify three equivalents in combinatorics.

Newton’s Identity

C(n,r) * C(r,k) = C(n,k) * C(n – k, r – k)

Here I am going to assume that n > r > k.

Hence:

C(n, r) * C(r, k)

= n! / (r! * (n – r)!) * r! / (k! * (r – k)!)

= n! / (n – r)! * 1 /  (k! * (r – k)!)

Rearrange:

= n! / k! * 1 / ((n – r)! * (r – k)!)

Multiply by (n – k)!/(n- k)!:

= n! / (k! * (n – k)!) * (n – k)! / ((n – r)! * (r – k)!)

Observe that (n – k) – (r – k) = n – k – r + k = n – r.  Hence,

= C(n,k) * C(n – k, r – k)   QED

Pascal’s Identity

C(n,r) = C(n-1, r) + C(n – 1, r – 1)

I’m going to start with C(n-1, r) + C(n – 1, r – 1)

C(n-1, r) + C(n – 1, r – 1)

= (n – 1)! / (r! * (n – 1 – r)!) + (n – 1)! / ((r – 1)! * (n – r)!)

= (n – 1)! / (r! * (n – 1- r)!) + (r * (n – 1)!) / (r! *(n – r)!)

= ((n – 1)! * (n – r)) / (r! * (n – r)!) + (r * (n – 1)!) / (r! * (n – r)!)

= (n * (n – 1)! – r * (n – 1)! + r * (n – 1)!) / (r! * (n – r)!))

= (n * (n  - 1)!) / (r! * (n – r)!)

= n! / (r! * (n – r)!)

= C(n, r)  QED

Combinatorial Proof

C(m + n, 2) – C(m, 2) – C(n, 2) = m * n

C(m + n, 2) – C(m, 2) – C(n, 2)

Note that 2! = 2

= (m + n)! / (2 * (m + n – 2)!) – m! / (2 * (m – 2)!) – n! / (2 * (n – 2)!)

= ( (m + n)! * (m – 2)! * (n – 2)! – m! * (m + n – 2)! * (n – 2)!  - n! * (m – 2)! * (m + n – 2)!) / (2 * (m + n – 2)! * (m – 2)! * (n – 2)!)

= ( (m + n) * (m + n – 1) *(m + n – 2)! * (m – 2)! * (n – 2)! – m * (m – 1) *(m – 2)! * (n – 2)! * (m + n – 2)! – n * (n – 1) * (n – 2)! * (m – 2)! * (m + n – 2)! )

/  (2 * (m + n – 2)! * (m – 2)! * (n – 2)!)

= ( (m + n)*(m + n – 1) – m * (m – 1) – n * (n – 1) ) / 2

= ( m^2 + m*n – m + m*n + n^2 – n – m^2 + m – n^2 + n) / 2

= (2 * m * n) / 2

= m * n   QED

Eddie

Source where I got the identities from:

V.K. Balakrishnan Schaum’s Theory and Problems: Combinatorics including concepts of Graph Theory  McGraw-Hill, Inc. New York: 1995  ISBN 0-07-003575-X

The derivation and proof details are my work.  

All original content copyright, © 2011-2018.  Edward Shore.   Unauthorized use and/or unauthorized distribution for commercial purposes without express and written permission from the author is strictly prohibited.  This blog entry may be distributed for noncommercial purposes, provided that full credit is given to the author.  Please contact the author if you have questions.

The Golden Ratio: Reciprocals and Powers

The Golden Ratio: Reciprocals and Powers

Determining the Golden Ratio

Take a line segment with length of x + 1, and split it into two segments, one with width x, the other width 1. (see the black lines on the left)

The golden ratio is defined when given positive numbers a and b, where a > b, the following ratio is true:

(a + b) / a = a / b

Applying this to the above diagram:

(x + 1) / x = x / 1

Solving for x yields:

(x + 1) * 1 = x * x

x + 1 = x^2

x^2 – x – 1 = 0

By the quadratic equation:

x = (1 ± √(1^2 – 4 * 1 * -1)) / 2

x = ( 1 ± √5 ) / 2   (I)

Since x is a measure, we will consider only the positive root and define the golden ratio (ϕ) as:

ϕ = (1 + √5) / 2    (II)

ϕ ≈ 1.6180339

Reciprocals of ϕ

1 / ϕ

1 / ϕ  

= 2 / (1 + √5)

= 2 / (1 + √5) * (1 - √5) / (1 - √5)

= 2 * (1 - √5) / -4

= (2 – 2 * √5) / -4

= (2 * √5 – 2) / 4

= (√5 – 1) / 2

Here is where a trick comes in, we’re going to add and subtract 1:

= (√5 – 1 + 1 – 1) / 2

Now, note that:

= (√5 + 1 – 2) / 2

= (√5 + 1) / 2 – 2 / 2

= (√5 + 1) / 2  - 1

= ϕ – 1

Hence:  1 / ϕ = ϕ – 1

1 / ϕ^2

1 / ϕ^2

= (2 / (1 + √5) )^2

= 4 / (6 + 2 * √5)

= 4 / (6 + 2 * √5) * (6 – 2 * √5) / (6 – 2 * √5)

= (24 – 8 * √5) / 16

= (3 - √5 ) / 2

Note that 4 – 1 = 3…

= (4 – 1 - √5) / 2

= 4 / 2 – (1 + √ 5) / 2

= 2 - ϕ

Hence:  1 / ϕ^2 = 2 - ϕ

Powers of ϕ

ϕ^2

ϕ^2

= ( (1 + √5) / 2 )^2

= 1 / 4 * (1 + 2 * √5 + 5)

= 1 / 4 * (6 + 2 * √5)

= (3 + √5) / 2

= (2 + 1 + √5) / 2

= 1 + (1 + √5) / 2

= 1 + ϕ

Hence:  ϕ^2 = 1 + ϕ

Take note, this plays in determining further powers of ϕ.

ϕ^3

ϕ^3

= ϕ * ϕ^2

Using the fact that ϕ^2 = 1 + ϕ

= ϕ * (1 + ϕ)

= ϕ + ϕ^2

= ϕ + 1 + ϕ

= 1 + 2 * ϕ

Hence:  ϕ^3 = 1 + 2 * ϕ

ϕ^4

ϕ^4

= ϕ * ϕ^3

= ϕ * (1 + 2 * ϕ)

= ϕ + 2 * ϕ^2

= ϕ + 2 * (1 + ϕ)

= ϕ + 2 + 2 * ϕ

= 2 + 3 * ϕ

With ϕ^4 = 2 + 3 * ϕ.   Moving on…

ϕ^5

ϕ^5

= ϕ * ϕ^4

= ϕ * (2 + 3 * ϕ)

= 2 * ϕ + 3 * ϕ^2

= 2 * ϕ + 3 * (1 + ϕ)

= 2 * ϕ + 3 + 3 * ϕ

= 3 + 5 * ϕ

Hence:  ϕ^5 = 3 + 5 * ϕ

ϕ^6

Quickly…

ϕ^6

= ϕ * ϕ^5

= ϕ * (3 + 5 * ϕ)

= 5 + 8 * ϕ

A Connection to the Fibonacci Sequence

Sense a pattern?

ϕ^2 = 1 + ϕ

ϕ^3 = 1 + 2 * ϕ

ϕ^4 = 2 + 3 * ϕ

ϕ^5 = 3 + 5 * ϕ

ϕ^6 = 5 + 8 * ϕ

Note the coefficients come from the Fibonacci Sequence.  (1,1,2,3,5,8,13…  )  The Fibonacci sequence is defined as:

F_n = F_n-1 + F_n-2   where the first two initial terms are 1 and 1.

Can we show that ϕ^n = F_n+1 + F_n * ϕ?

Proof

Let assume that the base case of:

ϕ^n = F_n-1 + F_n * ϕ

Will this relation hold up for ϕ^(n+1)?  Then:

ϕ^(n + 1)

= ϕ * ϕ^n

= ϕ * (F_n-1 + F_n * ϕ)

= ϕ * F_n-1 + F_n * ϕ^2

= F_n-1 * ϕ + F_n (1 + ϕ)

= F_n-1 * ϕ + F_n + F_n * ϕ

= F_n + (F_n-1 + F_n) * ϕ

Using the definition of the sequence, F_n-1 + F_n = F_n+1.  Hence:

= F_n + F_n+1 * ϕ

Since ϕ^(n + 1) = F_n + F_n+1 * ϕ, the relation holds.

Next time I have a retro review of an early financial calculator from the 1980s, the TI BA-II (without any plus or other annotation).  I have couple more retro calculator reviews coming (tentatively) later this month:  Casio CM-100 and Canon FS-5. 

That’s all for now!  Take care,

Eddie

This blog is property of Edward Shore, 2017.

Absolute Value: Does |x|^2 = x^2?

Absolute Value:  Does |x|^2 = x^2?

Proof that |x|^2 = x^2, assuming x is a real number.

Note that |x| = x/sgn(x), where sgn(x) is the sign function where:

sgn(x) = -1 if x < 0,

sgn(x) = 0 if x = 0,

and sgn(x) = 1 if x > 0

Case: x = 0. 

Then:

|0| = 0 and |0|^2 = 0^2 = 0.

Case: x ≠ 0.  

Then:

|x|^2 = (x/sgn(x))^2

= x/sgn(x) * x/sgn(x)

= x^2/sgn(x)^2

If x < 0, sgn(x) = -1, and since -1 * -1 = 1, sgn(x)^2 = 1

If x > 0, sgn(x) = 1, and since 1 * 1 = 1, sgn(x)^2 = 1

Hence:

x^2/sgn(x)^2

= x^2

QED

Caution:  The statement |x|^2 = x^2 is not true for complex numbers where the imaginary part is nonzero. 

Let x = a + b*i

|x|^2 = |a + b*i|^2 = (√(a^2 + b^2))^2 = a^2 + b^2

x^2 = (a + b*i)^2 = a^2 + 2*a*b*i – b^2 ≠ a^2 + b^2   (b ≠ 0)

Conclude:  |x|^2 = x^2 only if x is a real number.

Eddie

This blog is property of Edward Shore, 2016