Sums of second order and the value of mathematics

In summary, there are various methods for finding the sum of a sequence, but some may be more efficient than others. It is important to consider the practical application of these abstract methods before determining their value.
  • #1
verty
Homework Helper
2,194
198
Consider this sequence:

1, 2, 3, 4, 5, ...

We can calculate the n'th term of the sequence by the function t(n) = n. We could define s(n), the sum to n terms, recursively as s(1) = 1 and s(n) = n + s(n-1). The time bound of this procedure is O(n), but it isn't efficient because we can find an O(1) formula: s(n) = n(n+1)/2

Now consider this sequence:

1, 3=(1+2), 6=(1+2+3), 10, 15, 21, ...

Here the n'th term of the sequence is given by s(n) = n(n+1)/2, the same function as above. We can define u(n), the sum to n terms of this sequence, recursively as u(1) = 1 and u(n) = u(n) + s(n-1). This procedure has a time bound of O(n).

Can we do better than this? We can use simple variations, but the time stays linear. For example, where n>2, 'u(n) = u(n-2) + 2.s(n-1) + n' could be used. This nearly doubles the speed on average, but the time taken is still proportional to n.

Is there a method to calculate this sum in time less than proportional to n? As a matter of fact, we can do it in time which is O(logn).

s(n) = n(n+1)/2.

Where n = 1: u(1) = 1
Where n is even: u(n) = 2.u(n/2) + n.s(n/2)
Where n is odd: s2(n) = 2.u((n-1)/2) + ((n+1)/2) * [s((n-1)/2) + s((n+1)/2)]


In case you are wondering how I came up with these formulas, notice that (1) below corresponds to u(4). It can be split up into (2), which corresponds to 'u(2) + 2.s(2) + 3 + (3+4)'. In (3) you can see that '3 + (3+4)' can be split into u(2) + 2.s(2)


1: 1 + (1+2) + (1+2+3) + (1+2+3+4)

2: 1 + (1+2)
+ (1+2) + (1+2)
+ 3 + (3+4)

3: 3 + (3+4)
= 1 + (1+2)
+ 2 + (2+2)


Putting it together:

u(4) = u(2) + 2.s(2) + u(2) + 2.s(2)
= 2.u(2) + 2.(2.s(2))

This corresponds to:

u(n) = 2.u(n/2) + (n/2)(2.s(n/2))
= 2.u(n/2) + n.s(n/2)

I derived the formula for when n is odd the same way. I will now generalise this method to work for all arithmetic series:

t(n) = a+(n-1)d
s(n) = (n/2)[2a+(n-1)d]

f(n) = n(n+1)/2

where n = 1: g(n) = 1
where n is even: g(n) = 2.g(n/2) + n.f(n/2)
where n is odd: g(n) = 2.g((n-1)/2) + ((n+1)/2) * [f((n-1)/2) + f((n+1)/2)]

s2(n) = a.f(n) + d.g(n-1)


Let's call this the 'second sum'. I wonder whether it is possible to find a formula for the 2nd sum that isn't recursive. I don't think the 'second sum' as I have defined it has any application, because I can't envision any place where the second sum might be useful. Can this be applied somewhere? What about the 3rd or 4th sum?

Mathematics is only useful where it can be applied, or so I think. Does mathematics attain value only when you can apply it? This question is more philosophical than mathematical, I think. Is it only worthwhile to find formulas for such abstract things as the 'second sum' when we see the need for them?

The point of this post is because I don't see the value of such abstract things, unless they can be applied. Is this fair?
 
Mathematics news on Phys.org
  • #2
You can find the "second sum", but there's no fixed formula for it.

Each term in the series:
1, 3=(1+2), 6=(1+2+3), 10, 15, 21, ...
Is given by the formula:
[tex]a_{(n)} = \frac{n(n + 1)}{2} = \frac{1}{2}(n^2 + n)[/tex]
To find the sum of these terms, you need to find the sum of n times [itex]n^2[/itex], n times [itex]n[/itex], add them together and divide by two.

The sum of n times [itex]n[/itex] is simple, and you already found it yourself:
[tex]{S_1}_{(n)} = \frac{n(n + 1)}{2}[/tex]
It is the sum of n times [itex]n^2[/itex] you need to find now. I won't explain here how you get it (it's a bit length), but the formula is:
[tex]{S_2}_{(n)} = \frac{n}{6}(2n + 1)(n + 1)[/tex]

So the final "second sum" that you are looking for is:
[tex]S_{(n)} = {S_1}_{(n)} + {S_2}_{(n)} = \frac{1}{2}(\frac{n}{2}(n + 1) + \frac{n}{6}(2n + 1)(n + 1))[/tex]
You can simplify it if you want, but that's it. :smile:
 
  • #3
You might find find learning about difference equations useful
 

1. What is the significance of second order sums in mathematics?

Second order sums are a type of mathematical equation that involves the addition of squared terms. They are commonly used in various areas of mathematics, including calculus and statistics. These sums allow us to analyze and understand complex relationships between variables in a given system.

2. How are second order sums calculated?

To calculate a second order sum, you must first identify the squared terms in the equation. Then, you square each term and add them together to get the final result. For example, in the equation x^2 + 2xy + y^2, the second order sum would be (x^2 + y^2).

3. What is the relationship between second order sums and polynomials?

Second order sums are closely related to polynomials, as they both involve the addition of terms with exponents. In fact, a second order sum can be considered a special case of a polynomial with a degree of 2. This connection allows us to use polynomial techniques to solve problems involving second order sums.

4. How do second order sums contribute to understanding mathematical concepts?

Second order sums play a significant role in understanding mathematical concepts such as quadratic equations and functions. They allow us to model and analyze real-world phenomena, make predictions, and solve problems in various fields such as physics, economics, and engineering.

5. Can second order sums be applied in other fields of study?

Yes, second order sums have applications in many different fields, including computer science, biology, and chemistry. They are also used in data analysis and machine learning algorithms. The principles and techniques learned from studying second order sums can be applied to various problems and systems in these fields.

Similar threads

  • General Math
Replies
2
Views
1K
  • General Math
Replies
8
Views
1K
Replies
1
Views
909
  • General Math
Replies
4
Views
2K
Replies
7
Views
1K
  • General Math
Replies
1
Views
1K
Replies
6
Views
943
  • General Math
Replies
9
Views
1K
  • General Math
Replies
7
Views
1K
Replies
3
Views
620
Back
Top