Polynomial Fitting for Sequences [Discrete Math Class]

Note that this video is part of a series kept in a playlist called [Discrete Math Class]:

If you like this video, please consider subscribing to my channel and let me know in the comments if you'd like to see more like this.

This textbook for the course is the open-source textbook by Oscar Levin:

#combinatorics #sequences #closedformula #closedform #recurrence #recursion #recursiveformula #polynomial #polynomialsequence #polynomialfitting #summation #sigma #summationnotation #sigmanotation #partialsums #sums #math #manim #discretemathematics
#differenceoperator #kdifferences #differencesequence #constant

To learn more about animating with manim, check out:

_______________________________________
Background Music:

[resultingrun]

Fantastic. I was doing this the past few days. And then I get to see it given a name and expanded on.

[zengakukatsu]

This was actually the first thing I tested with the partitions of n sequence (I didn't actually start with the triangle, I went backwards from what I explained) and it did NOT work lol. Great video!

[Tezhut]

Cool! Just covered this in my class, up to degree 2 only in 9th grade. There we do use the differences for getting a system of equations, because in that case it usually simplifies a lot. And the kids didn't take linear algebra.

[dungdul]

This is the best visual proof for sum of n^2 I've ever seen. Thank you so much!
BTW, is there any way to understand why when the sequence of delta^k(a) is constant, we know that there must be an explicit formula which is a degree-k polynomial?

[jakobr_]

Is there a way to find the polynomial using the first term of each delta, instead of the first n terms of the sequence? It seems arbitrary to me that we choose to use those four points of the sequence instead of, say, S5 through S8 or S10, S23, S24, and S99. Meanwhile there are four and only four starting points of these four sequences. Seems to me like those would be the more “natural” bits of info to use to find the coefficients.

[pion]

Instead of using a calculator, it's easier to line up the first term in each row multiplied with the corresponding binomial of that order (the first term is zero, but I'll leave it for clarity): (n choose 0)*0 + (n choose 1)*1 + (n choose 2)*3 + (n choose 3)*2 = 1/3 (n - 2) (n - 1) n + 3/2 (n - 1) n + n = 1/6 n (2 n^2 + 3 n + 1) = n^3/3 + n^2/2 + n/6. I left some intermediate steps. You're probably aware of that trick, but I use it all the time when hunting for closed polynomials for sequences.

[tamoozbr]

Finding d is actually really simple, since D(0) = d, since all the other terms amount to 0