Pascal's triangle, programming and Fourier | Tangente

Binomial coefficients, ubiquitous throughout mathematics and particularly in combinatorics and probability, are defined by

where k and n are integers such that 0 ≤ k ≤ n.

Pascal's triangle is constructed using the following property:

In other words, if the rows and columns are numbered from 0 to n, the entry in row n + 1 and column k + 1 is the sum of the entry directly above it (row n, column k + 1) and the preceding entry (row n, column k). These coefficients are used in a wide variety of fields: for example, to expand (x + y)*ⁿ using Newton's binomial theorem, to calculate probabilities associated with a random variable following a binomial distribution, or to determine the Bernstein polynomials used to construct Bézier curves… Pascal's triangle can even be used in analysis when working with functions involving a power, such as t ?2^n-*¹ (cost)*ⁿ where n* is a natural number. Such periodic, integrable functions can be viewed as signals (sounds, videos, etc.) and therefore manipulated as such for various applications, including compression and information transmission…

An essential step in these applications is to calculate the signal's Fourier transform. If f is an integrable function on $\mathbb{R}\backslash mathbb\{R\}$, the Fourier transform of f is the function

This operation takes us from an integrable function viewed as a signal to another function describing the signal's physical characteristics (its amplitude, phase and frequency).

All the calculations will be performed using the fx-CP400+E computer algebra calculator\. It has a computer algebra system (CAS), enabling it to perform symbolic calculations—for example, x + x = 2x—without assigning a value to x*.

The fx-CP400+E computer algebra calculator will make our task easier: first, we can run a program that depends on n; then calculate the Fourier transforms of the functions t ?2*^n-*¹ (cost)*ⁿ; and finally evaluate sums with upper limit n. We can do all this for several values of n, using ordinary mathematical notation and without having to rewrite the calculations at each stage. Raising the function's expression to the power n naturally brings in the binomial coefficients when cos t is written as (e^{i t} + e^{–i t}*) / 2.

Let us begin by writing a program that generates the first n rows of Pascal's triangle. Go to the **Program menu

**.

Create the program below by pressing Edit, followed by New File.

The number n can be entered directly in the program parameters (at the top right, circled in red), allowing the program to be used from the Main menu. This gives us an overview of all our calculations: the Fourier transforms and Pascal's triangle.

Here are a few comments and explanations:

• Ident(n) generates the identity matrix of size n;

• A[l, k] is the entry in the l^th row and k^th column of A. We use the fact that A[l, k] is the sum of the entry directly above it, A[l – 1, k], and the preceding entry, A[l – 1, k – 1]. We could also have designed a program using binomial coefficients. The corresponding key,

, can be found on the Advanced keyboard;

• Pascal's triangle is stored in matrix A; a message will display this information when the program is run.

The fx-CP400+E computer algebra calculator offers five definitions of the Fourier transform. Here we select the Mathematical format in the settings

of the Main  menu.

Next, let us calculate the Fourier transform of the function t ?2*^n-*¹ (cost)*ⁿ for several values of n*. The Fourier transform can be found on the Advanced keyboard.

Each time, we display the first n + 1 rows of Pascal's triangle; the final row gives the binomial coefficients $\left(\begin{array}{c}n\\ k\end{array}\right)\backslash begin\{pmatrix\}n\backslash \backslash \backslash \; k\backslash \backslash \backslash end\{pmatrix\}$.

It is easier to write all the calculations in terms of n, as shown below. We then need only change the value of n at the beginning, and the calculator repeats all the calculations.

For n = 5, we obtain (the function $\delta \backslash delta$ denotes the Dirac delta function, defined by $\delta \backslash delta$(0) = 1 and $\delta \backslash delta$(x) = 0 for every nonzero real number x):

Similarly, for n = 8, we obtain:

Even without knowing what a Fourier transform is, we can formulate a conjecture from the two preceding results. We find that:

Let us check this relation using the calculator (Expand is the calculator feature used to expand an algebraic expression; here it distributes $\pi \backslash pi$):

The observed relation is indeed a general mathematical result, as the fx-CP400+E computer algebra calculator confirms.