Articles
BY OUR STUDENT CONTRIBUTORS
Nitya Nigam As promised in March 22nd’s Problem of the Week (apologies for the delay, it’s been a busy month), this is an article explaining the connection between choose functions and polynomial functions. More specifically, we’re going to prove why sequences of the form T_n = nCk (where k is a constant integer) are equivalent to specific polynomial sequences of degree k, as well as find the specific polynomial sequence that fits our POTW. While we will be showing this algebraically, there is also a very interesting analogy to Pascal’s Triangle that shows this, which we’ll leave to our readers to think about (and share their ideas about in the comments!) The example used in our POTW was T_n = nC3 for n≥3. The first few terms of this sequence are 3C3=1,4C3=4, 5C3=10, 6C3=20. We can observe that the differences between consecutive terms (what we call the “first difference”) are 1, 3, 6, 10. While some of you may already have noticed that this sequence is the triangle number sequence, we can go a step further, observing that the difference between these differences (the second differences) are 2, 3, 4 so the third difference is constant at 1. When a sequence has its kth difference constant, the sequence can be written as a polynomial. We can prove this using basic calculus. Say we have a polynomial sequence of the following form: When we differentiate this, the constant term disappears, and the powers on the rest of the terms decrease by 1, giving: When we differentiate this k times, we get: As this expression doesn’t contain any n terms, the kth derivative of a kth-degree polynomial sequence is constant. As the kth difference is simply the rate of change between integer terms, and the kth derivative is the rate of change in general (which is independent of the value of n, so will apply to integers), the two are equal. Therefore, we have shown that the kth difference of a polynomial sequence is constant, and that it is equal to k! times the coefficient on the n^k term. In our example, the third (or kth, as k=3) difference is 1. Since k! x a_0 = 1, a_0 = 1 / k! = 1 / (3x2) = 1/6. Now that we have the leading coefficient, we can simply use simultaneous equations (by plugging in the first three values of n [3, 4, 5]) to obtain the other coefficients. We’ll leave the process of simplifying and solving these equations to you (or your graphic calculator). The result you should get is a_1 = -1/2, a_2 = 0 and a_3 = 1/3, giving the following definition: After showing this analytically for the case k=3, let’s generalise. Sequences of the form nCk can be written, from their definition, as: The first difference of these sequences will be T_(n+1) – T_n: Now, if we’ve shown that the first difference of a sequence nCk is nC(k-1), then by extending this downwards by applying the same thing to the first difference sequence, we can say that the second difference is nC(k-2), and the kth difference is nC(k-k) = nC0, which is just 1. Since the kth difference is constant (which is the condition for a kth-degree polynomial sequence), these sequences can be written as polynomial sequences using the technique described above.
We hope you enjoyed this article, especially since it contained original mathematical ideas from us! Let us know in the comments if you see the link to Pascal’s Triangle, and tell us what you’d like to read next!
0 Comments
Leave a Reply. |
Our AuthorsWe are high school and college students from around the world who are passionate about maths, and want to share that passion with others. Categories
All
|