Some people have a natural gift for noticing patterns in numbers and may actually conjecture the formula with ease. Others may struggle with this approach at first but after practising with a variety of problems may discover that finding the formula can be an almost enjoyable task.
Tips for finding the formula:
- List about 3-5 iterations of the relation. On your first pass, don't sum or calculate products or simplify the expression. The pattern may be easier to see with the expression in this form. If no pattern is obvious, then simplify.
- Identify which values remain constant in each iteration.
- Identify which values change with each iteration.
- Do you notice a sum of values? A product? Is the product some value raised to an exponent/power?
- Identify the relationship between the number of the iteration and the changing values.
Example:
Suppose we would like to find a recurrence relation for \(s_0 = 3, s_k = s_{k-1} + 2k\) for all integers \(k >=1\)
\(s_0 = 3\)
\(1^{st}\) iteration: \(s_1 = 3 + 2.1\)
\(2^{nd}\) iteration: \(s_2 = 3 + 2.1 + 2.2\)
\(3^{rd}\) iteration: \(s_3 = 3 + 2.1 + 2.2 + 2.3\)
From this we can see that the first term, 3, remains constant and 2 is a factor of the remaining terms. So we get
\(s_0 = 3\)
\(1^{st}\) iteration: \(s_1 = 3 + 2(1)\)
\(2^{nd}\) iteration: \(s_2 = 3 + 2(1 + 2)\)
\(3^{rd}\) iteration: \(s_3 = 3 + 2(1 + 2 + 3)\)
The values inside the brackets change on each iteration and here we have a sum of terms. But how do we generalise? Well we look for a relationship between the number of the iteration and our changing values. In this example, in our \(k^{th}\) term we have 1 + 2 + ...+ k. This is the sum of an arithmetic sequence where a = 1 and d = 1. The sum of the first k terms in an arithmetic sequence is given by \(\frac{k}{2}(2a + (k-1)d)\).
Since a = 1 and d = 1 then. \(1 + 2 + ... + k = \frac{k(k+1)}{2}\)
So our final solution is
\(s_n = 3 + 2 \frac{n(n+1)}{2}\)
\(s_n = 3 + n(n+1)\)
\(s_0 = 3\)
\(1^{st}\) iteration: \(s_1 = 3 + 2.1\)
\(2^{nd}\) iteration: \(s_2 = 3 + 2.1 + 2.2\)
\(3^{rd}\) iteration: \(s_3 = 3 + 2.1 + 2.2 + 2.3\)
From this we can see that the first term, 3, remains constant and 2 is a factor of the remaining terms. So we get
\(s_0 = 3\)
\(1^{st}\) iteration: \(s_1 = 3 + 2(1)\)
\(2^{nd}\) iteration: \(s_2 = 3 + 2(1 + 2)\)
\(3^{rd}\) iteration: \(s_3 = 3 + 2(1 + 2 + 3)\)
The values inside the brackets change on each iteration and here we have a sum of terms. But how do we generalise? Well we look for a relationship between the number of the iteration and our changing values. In this example, in our \(k^{th}\) term we have 1 + 2 + ...+ k. This is the sum of an arithmetic sequence where a = 1 and d = 1. The sum of the first k terms in an arithmetic sequence is given by \(\frac{k}{2}(2a + (k-1)d)\).
Since a = 1 and d = 1 then. \(1 + 2 + ... + k = \frac{k(k+1)}{2}\)
So our final solution is
\(s_n = 3 + 2 \frac{n(n+1)}{2}\)
\(s_n = 3 + n(n+1)\)
Depending on the complexity of the recurrence relation you may not be able to conjecture a formula easily but there are methods for solving recurrence relations that involve identifying the type of recurrence relation and using an appropriate known closed-form formula.See this article for more details.
Good stuff!!! Like the tips
ReplyDeleteConcerning : 1+2+...+k=k(k+1)/2
ReplyDeleteWould like to know why is the expression all over 2?
Thanks for your question Aisha.
Delete1+2+...+k is the sum of an arithmetic sequence where the first term a = 1 and the common difference d = 1.
The sum of the first k terms in an arithmetic sequence is given by \(\frac{k}{2}(2a + (k-1)d)\). Substituting values a = 1 and d = 1 gives the sum as \(\frac{k}{2}(2 + (k-1)) = \frac{k}{2}(k+1)\).
I've updated the post with this information.