Also with high enough degree you could have any number as the next, funny too

"What do you think the next number is?" "A billion." "What? No, it isn't!" "Sure it is. Here's the formula." *shocked pikachu face*

I see that a lot on Quora. Some people find it funny. (I don't)

Overfitting... 😈

@@volodyadykun6490 easiest example (f(n)-f(n)*(-1)^(5-n))/2 to gobble up everything past it and by the same logic could add any value at any specific place in the sequence (by a second function (x)=k cut at both ends the exact same way ), you could get to the formula yourself even without too much education, just some practice doing math magic. 'tho higher education would definitely help.

Same here and I didn't know it was Newton!

Michael Scott is a top salesman, best boss, AND a mathematical genius?

Michael Scott.. You..?

what kind of school were you in?? algebra didnt start till 6th grade in most schools

I did it too with the recurrence relation, except I don't really know what a characteristic polynomial is in that context. I wrote u_{n+1} = u_n + 3n +1, and I recognized that it would be a sum of an arithmetic sequence (with r=1) and an arithmetic series (with r=3). You then have u_n = n + n*3*(n-1)/2 = 3/2n^2 + 1/2n as we know

I can only think of one other case of someone writing “Wow!” in the margin and some people think that was aliens, so your method must’ve been pretty unusual 😂

@@jonasdaverio9369 Sorry! Got my terminology mixed up. It's supposed to be the characteristic equation. Or is it the same thing? It's been 20 years. In short, substitute a_{n}=cr^n and find the roots. I came up with the recurrence relation P_{n}=P_{n-1}+3n-2, P_{1}=1. The associated homogeneous equation is P_{n}=P_{n-1}. Its solutions are of the form P^{(h)}_{n}=P_{n-1}=\alpha1^n. For the particular solution I assumed P_{n}=an^2+bn+c, ended up with the equation an^2+bn+c=a(n-1)^2+b(n-1)+c+3n-2, simplified to (-2a+3)n+(a-b-2)=0, got a=1.5, b=-0.5 and finally P^{(p)}_{n}=1.5n^2-0.5n. P_{n}=P^{(h)}_{n}+P^{(p)}_{n}=1.5n^2-0.5n+\alpha1^n. P_{1}=1 gives \alpha=0.

ohh was that topic on Finite Differences by any chance related to time series analysis?

It's not really suspicious. It's one of the foundation of numerical analysis. You can look at finite difference method, finite element method, Z transform, discrete Fourier transform, etc... All of which are of critical importance in engineering and science (simulation, control theory, signal theory)

That's exactly what it is. Babbage's difference engine used (or would have used, had it been built in his lifetime) truncated power series of various special functions to calculate their values to high precision and thus tabulate them, primarily for navigation, which used a lot of trig functions for example. We know sin x is x - x^3/6 + x^5/120 = ... which is amenable to iteration using Newton's method of differences. Babbage's engine was capable of evaluating polynomials up to degree seven to 31 decimal digits of precision.

You will probably find this link useful. :) en.wikipedia.org/wiki/Umbral_calculus#Umbral_Taylor_series

It actually is a derivative, because, in the end, it is rate of growth. The first one of the first derivative, aka rate of growth of out series. The second one if the second derivative, aka rate of growth of the rate of growth etc. In the example where the polynomial is a second degree one, then it means that the second rate of growth is standard, meaning that the initial sequence keeps increasing with "speed" that keeps increasing (accelerating) on a standard value. It becomes more obvious when you take the third derivative, which would be 0, aka the second derivative doesn't change, it's constant. The third differences are exactly that. Zeros. It is exactly rate of growth, simplified over every value of X.

You're correct. The analog of antiderivative is the falling factorial

Thanks. I've added this to the description.

Mathologer has a video on it: m.kzfaq.info/get/bejne/aqeliZxksbW0k3k.html

*This actually works for ANY of those number sequence questions!* By merely exercising the finite differences, then adding the next number up, you instantly PROVE that your calculated number IS in fact the next number following that logic! The person who asked you to figure out the missing number might've had a different logic in mind... but that's not your problem, is it now? 😌

I'm glad!

Just in the comments like this. That Sangakus stuff is interesting.

Haha! About 15 years?

@@singingbanana Well, I've only been watching for about half of that! 😆

kzfaq.info/get/bejne/ot6GY62Xq7TZmac.html

I think the relevant youtube link is at v=lxV0JfFNuis at time code 13:28

You can try the Mathologer video - m.kzfaq.info/get/bejne/aqeliZxksbW0k3k.html

Did you try working it out yourself, along with the video? I found my understanding came from expanding the sequence to the left and making a rough plot of the graph of all the levels of differences. Reading is one thing, but true understanding comes from doing it yourself.

It converges point-wise, as for any n, for all K >= n, a(n) = sum(k=0..K)[(∆^k a)(0) * {n choose k}. I think uniform convergence only holds for polynomial sequences though. This is still a nice tool to get some identities involving sums of binomial coefficients if we utilize patterns in infinite sequences of differences: (∆^k a)(0) = 1, 1, 1, ... a(n) = 2^n sum(k=0..n)[{n choose k}] = 2^n (∆^k a)(0) = 1, x, x^2, ... a(n) = (x+1)^n sum(k=0..n)[{n choose k} * x^k] = (x+1)^n (∆^k a)(0) = 1, -1, 1, -1, ... a(n) = 0^n sum(k=0..n)[{n choose k} * (-1)^k] = 0^n

I saw that, and considered presenting this video as a magic trick. But decided against it in the end.

The differences don’t have to be the same… it depends on the sequence. See the Mathologer video: m.kzfaq.info/get/bejne/aqeliZxksbW0k3k.html

That's amazing! I stumbled upon this when I was looking for a fast circle drawing algorithm. I was really proud of myself up until the point when my research uncovered Bresenham algorithm. Turns out he discovered circle drawing algorithm *in addition to* line drawing algorithm! Previously, I had to use Calculus to solve it. So, it's arithmetic problem, after all.

Yes - m.kzfaq.info/get/bejne/aqeliZxksbW0k3k.html

Yes, this video is perfect for you. The sequence 1^n, 2^n, 3^n, 4^n, etc. comes from plugging the values x = 1, x = 2, x = 3, x = 4, etc. into the polynomial f(x) = x^n. You can then look at what James does in this video from 4:30 - 5:46. The nth order differences (which I imagine you are considering to be the (n+1)st step) will result in a constant sequence where the constant is n! times the leading coefficient of the polynomial. Indeed, since the leading coefficient of f(x) = x^n is just 1, you will, indeed, get n!. So yeah, this video completely explains the pattern you have been noticing. Quite astonishing how that works out :)

I had found this exact phenomena a long time ago as well and was blown away! Good job on finding it -- I proved it many years later using some bipartite graph matching argument to prove a combinatorial identity: \Sum_{i=0}^n [(-1)^(n-i)*(n choose i)*(k+i)^n] = n! for any k,n -- turns out it's a very similar problem. That said, I think this video gives a much simpler analytical argument at: kzfaq.info/get/bejne/qcmBaJSixJfSmKs.html. Here your sequence is just f(x) = a_n*x^n, with a_n = 1 for all n. Thus after the n^th difference, you're left with D^n(x) = n!

I think you can use binomial expansion on (n+1)^m and n^m and see the difference, should get you a recurrence relation for lower m.

Eventually you will get down to one - the point of the downward triangle. That will automatically be constant with itself, and you will have a polynomial of the order of the number of items in the sequence. Note that you could extend the sequence with any one number in fact. All that would happen is that the coefficients would change.

Someone asked a similar question in another comment, and I thought about it and came up with some answers. "when you truly have a "constant" sequence at n-th order: how do we know it will be constant for all time?" Yeah, the problem is you don't. I was able to devise a method to come up with a sequence where the nth order differences has an initially constant string of length k, for any positive integers n and k you want, but the sequence doesn't satisfy a polynomial. To do this, you can fix a polynomial f(x) of degree n. Then take the beginning of your sequence to be f(0), ..., f(n+k-1). From there, you pick some other thing, like a different polynomial g(x) (which doesn't agree with f(x) at x = 0, x = 1, ..., or x = n+k-1), then you choose the rest of your sequence to be g(n+k), g(n+k+1), g(n+k+2), ... The sequence cannot possibly satisfy a polynomial relationship. If did, since that polynomial would agree with g on infinitely many points, it would have to be equal to g. But the full sequence cannot match with g, by how the sequence is chosen. Now, since the first n+k terms of the sequence come from a degree n polynomial, when you get to the nth order differences, you will get a constant string of length k. So yeah, you can't tell whether the sequence actually satisfies a polynomial just by getting a really long constant string. Because you can cook up non-polynomial sequences with arbitrarily long constant strings. But it seems you expected that! After all, you suggest: "I guess if we prove that the sequence must take on integer values of some polynomial, then the polynomial must have constant n-th order differences" I decided to look into this too! If you can prove that the sequence must satisfy a polynomial relationship, it's still _not_ good enough. Because you can use the same sort of recipe to create counterexamples here, too. What I mean by this is you can create a polynomial sequence where the nth order differences has a constant string of length k, but changes in the kth position. Being a polynomial sequence, it will, eventually, reach a constant sequence, but it will be further along. To do this, you start again with a polynomial f(x) of degree n, and you choose the beginning of your sequence to be f(0), ..., f(n+k-1). Just like in the previous example, this guarantees that with the nth order differences, you get a constant string of length k. But then what you do is you pick any number c, other than f(n+k), and make it the next term of the sequence. You now have n+k+1 points: (0,f(0)), ..., (n+k-1,f(n+k-1)), (n+k,c). These n+k+1 points pin down a polynomial g(x) of degree n+k passing through them. But by this construction, we have g(0) = f(0), ..., g(n+k-1) = f(n+k-1), and g(n+k) = c, so all terms of the sequence constructed so far satisfy g. Then you just use g to get the rest of the sequence. So the sequence _is_ a polynomial sequence, but it has a sort of "false start" of length k at the nth order differences, since g(x) agrees with a degree n polynomial f(x) for the first n+k terms of the sequence. And, of course, you can create multiple "false starts" by continuing with g for a while, then repeating the process with a new polynomial h, etc. So you can create a polynomial sequence with an arbitrary number of arbitrarily long initial constant strings. So, even _knowing_ that you have a polynomial sequence, just getting several terms constant in a row in some difference sequence is not enough to conclude that you have found the polynomial relationship. Proving it's polynomial is not enough! But if you can prove your sequence satisfies a polynomial of degree n, then yeah, that's good enough. Because you know the nth order differences _must_ be constant then. In practice, how I imagine this works, is that you have some scenario you're trying to find a sequence for (like the pentagonal numbers, as in the video). You can try the finite difference method and get to a seemingly constant sequence, and then develop a polynomial from there. But then you have to prove that your polynomial really works for the full sequence in the scenario you care about. Having a candidate polynomial actually gives you a *_monumental_* leg up on proving what you want :)

So what this excersice does, is basically take the derivative of the underlying formula. I'm not sure if you have any calculus under your belt, but imagine that he did this excersice of a sequence of numbers like 1,4,7,10,13,16... So the first order difference is always 3. If you imagine those points as a graph, it will be a straight line pointed up to the right. So in my example the rate of change is 3. But because the polynomial that describes a line is consistent from infinity to negative infinity we can know that the rate of change won't change. It will stay a line with the same slope. I'm his example he has to get to the 2nd irder differences, because the rate of change (1st order) is also changing. However, if you can get to a difference that remains constant, you can know it will stay that way because it describes a line. To my knowledge this only works with polynomials though due to the way the derivitaves are calculated.

True. And you can get that from the Newton Formula in this video. Because D^(0)(0) = 0, D(0) = 1, and D^2(0) = n -2, and the Newton formula does the rest.