Skip to main content

Latest Post

Power Essence Coefficients and Bernoulli Numbers

Previously, we have explored methods to compute the essence of power functions $Ȣx^n$ which involves solving a large system of linear equations. This method is equivalent to solving for the inverse of a large $n\times n$ matrix where entries are values of pascal's triangle. Though the matrix method allow us to solve for large number of essences at once, it does not extend easily to solve for next iterations of essence coefficients. Rather than reusing the values we have already solved for, we will have to solve for inverse of a separate larger matrix again. Here we will introduce an iterative method for solving for these coefficients. Chapter 0: Recap Let us first remind ourselves of the definition of essence. For a function $f(x)$, we want to find the transformation $Ȣf(x)$ such that we are able to 'smooth out' its series: $$\sum_{i=a}^b f(i) = \int_{a-1}^b Ȣf(x) dx$$ For example, we can solve for the following functions: $$\begin{align*}Ȣ1 &= 1 \\ Ȣx &= x +

Summation of Harmonic Interval and Simplified Riemann Sum

When you first learn of Summation in Pre-Calc class, it is probably in build-up to Riemann Sum.
You are taught the basics of Summation and simple manipulations, such a $\sum_nc*a_n = c*\sum_na_a$ for constant $c$, but you don't get to explore deeper into Summations and really play around with it.
One thing that really intrigued me was why Summations only incremented by a unit. When we have a Sum like $\sum_{n=3}^{10}a_n$, it is equal to $a_3+a_4+a_5+\dots+a_9+a_{10}$, always incrementing by a unit( $1$ ).

Why couldn't we Sum with interval that is not a unit? How could we have something like $a_3+a_{3.5}+a_4+a_{4.5}+a_5+a_{5.5}+\dots+a_{8.5}+a_9+a_{9.5}+a_{10}$, incrementing by a half instead of a full unit?

Sets

Of course you technically can use Sets and Set Builder Notation to create a specific Summation.
$$\sum_{i \in S}i,S=\{\frac{x}{2}|x\in\mathbb{N_0}\} \, = \, 0+\frac{1}{2}+1+\frac{3}{2}+\dots$$
The above is Sum of all Rational Numbers incrementing by $\frac{1}{2}$ rather than typical $1$ written with Set Notations.
However, this wasn't what I was looking for; I wanted a way to increment through the bounds set by Sigma symbol and without defining or using Sets.


Increment Manipulation

Most of obvious Summation Rules only deals with the inner term, the $a_i$. Some examples are
$$\sum_{i=n}^mca_i=c\sum_{i=n}^ma_i, \text{where $c$ is constant relative to $i$}\\
\sum_{i=n}^m{a_i+b_i}=\sum_{i=n}^ma_i+\sum_{i=n}^mb_i$$
The few Rules that deal with the bounds, the $m$ and $n$, only really deals with addition and subtraction of the bounds:
$$\sum_{i=n}^ma_i = \sum_{i=z}^ma_i+\sum_{i=n}^za_i, z\in [n,m]\\
\sum_{i=n}^ma_i=\sum_{i=0}^ma_i-\sum_{i=0}^{n-1}a_i\,, m > n$$
When you start experimenting with multiplication and scaling of bounds, you will find a interesting result.
Take a look at the following:
$$\sum_{i=kn}^{km}a_{\frac{i}{k}}\,,k\in \mathbb{N}$$
The bounds have been multiplied by $k$ while index $i$ inside the term have been divided by $k$.
This uses the same definition of Sigma Summation as above, incrementing technically by a unit each time, but let's look at how the results differ due to $k$:
$$\sum_{i=kn}^{km}a_{\frac{i}{k}}=a_{\frac{kn}{k}}+a_{\frac{kn+1}{k}}+a_{\frac{kn+2}{k}}+a_{\frac{kn+3}{k}}+\dots+a_{\frac{km-2}{k}}+a_{\frac{km-1}{k}}+a_{\frac{km}{k}}$$
The first index starts with $kn$, but because index is divided by $k$, the first term becomes simple $a_n$.
The second term's index is $kn+1$, but because of $\frac{1}{k}$, it simplifies to $n+\frac{1}{k}$. The index effectively incremented not by a unit but by $\frac{1}{k}$.
This continues as the third term is $a_{\frac{kn+2}{k}} = a_{n+\frac{2}{k}}$, and fourth $a_{\frac{kn+3}{k}} = a_{n+\frac{3}{k}}$ and so on.
Each time the index $i$ is incremented not by $1$ but by $\frac{1}{k}$ from bounds $n$ to $m$.
$$\sum_{i=kn}^{km}a_{\frac{i}{k}} = a_n+a_{n+\frac{1}{k}}+a_{n+\frac{2}{k}}+a_{n+\frac{3}{k}}+a_{n+\frac{4}{k}}+\dots+a_{m-\frac{3}{k}}+a_{m-\frac{2}{k}}+a_{m-\frac{1}{k}}+a_m\,,k\in  \mathbb{N}$$
Using this, we have a easy method of representing a Sum with Harmonic Fraction (Unit over Natural Number) increments:
$$\begin{align*}0+1+2+3+4+\dots+8+9+10&=\sum_{i=0}^{10}i
\\0+.5+1+1.5+2+2.5+\dots+8+8.5+9+9.5+10 &= \sum_{i=2*0}^{2*10}\frac{i}{2}\\0+\frac{1}{3}+\frac{2}{3}+2+\frac{4}{3}+\dots+9+\frac{28}{3}+\frac{29}{3}+10 &= \sum_{i=3*0}^{3*10}\frac{i}{3}\end{align*}$$

As we increase value of $k$, the interval between each term becomes finer and finer. This can be very useful when dealing with Riemann Summation.

Righthand Riemann Sum

The idea of Riemann Summation is simple: use rectangles to approximate the area under a curve over a interval.
We will first talk about Righthand Riemann Sum, and mention other types of Riemann Sums later.
Riemann Sum can be broken down as such:
$$\sum_{\text{Boundary}}(\text{Width of Interval})*(\text{Height of Interval})$$
Riemann Sum is only a approximation, but as the Intervals get thinner and thinner, the approximation approaches actual Integral Value.
This is where we get the ugly formula:
$$\int _n ^m f(x) dx = \lim_{a\rightarrow \infty}\sum^a_{b=1}\frac{m-n}{a}f(n+b\frac{m-n}{a})$$
This is the formula taught in my pre-calc class.
The $\frac{m-n}{a}$ represents Width and $f(n+b\frac{m-n}{a})$ represents Height of an interval.
This formula, however, is very wordy and intimidating to many students.
Is there a way to make this simpler and more elegant?

What bothers me the most in the formula above is how boundary isn't part of Sigma's upper and lower bound, but whether a part of the inner term itself.


Modified Riemann Summation

Let's build a Riemann Formula using Increment Manipulation.
$$\sum_{i=kn+1}^{km}\frac{1}{k}f(\frac{i}{k}), k \in \mathbb{N}$$
This formula sums up $k$ number of Rectangles for each unit. This means you will be summing up $k(m-n)$ rectangles with this Summations.
 The Width of the rectangle is equal to the increment, $\frac{1}{k}$ and Height of the rectangle is determined by $f(\frac{i}{k})$. The lower bound is $kn+1$ instead of $kn$ because this Sum is set to be Riemann Righthand Summation.

As $k$ becomes larger and larger, each interval becomes thinner and thinner and yields more accurate approximation of actual Integral. Using that, we can craft a new definition of Riemann Sum as such:
$$\int _n ^m f(x) dx = \lim_{k\rightarrow\infty}\sum_{i=kn+1}^{km}\frac{1}{k}f(\frac{i}{k})$$
We can further simplify the formula as such:
$$\int _n ^m f(x) dx = \lim_{k\rightarrow\infty}\frac{1}{k}\sum_{i=kn+1}^{km}f(\frac{i}{k})$$
This formula is much simpler and cleaner to use than the messier $\lim_{a\rightarrow \infty}\sum^a_{b=1}\frac{m-n}{a}f(n+b\frac{m-n}{a})$, so it may be even easier to use this definition rather to calculate an integral. 

Lefthand and Trapezoid Riemann Summation

So far, we only worked with Righthand Sum, but there are two more major types of Riemann Sum: Lefthand Sum and Trapezoid Sum. We can simply those two like we Simplified Righthand Sum:
$$\begin{align*}\text{Righthand} \,=& \lim_{k\rightarrow\infty}\frac{1}{k}\sum_{i=kn+1}^{km}f(\frac{i}{k}) \\
\text{Lefthand}\,=& \lim_{k\rightarrow\infty}\frac{1}{k}\sum_{i=kn}^{km-1}f(\frac{i}{k})\\
\text{Trapeoid}\,=& \lim_{k\rightarrow\infty}\frac{1}{k}\sum_{i=kn+1}^{km}\frac{f(\frac{i-1}{k})+f(\frac{i}{k})}{2} =& \lim_{k\rightarrow\infty}\frac{1}{k}\sum_{i=kn}^{km-1}\frac{f(\frac{i}{k})+f(\frac{i+1}{k})}{2}
\end{align*}$$
All these are just definitions of each types of Riemann Sum all trying to approximate actual Integral, but how do we know if they are all approximating the same value?
We have to first be sure that each of these forms are equal to each other or, at least, under what conditions these Sums are equal to each other.

$$\text{Righthand Sum} = \text{Lefthand Sum} \Leftrightarrow \text{Difference of Endpoints is Finite}$$

First, let's break down each Sum into simpler parts:
$$\begin{align*} \text{Righthand} \,=& \lim_{k\rightarrow\infty} \frac{1}{k} \sum_{i=kn+1}^{km}f(\frac{i}{k})\\
=&\lim_{k\rightarrow\infty} \frac{1}{k} (\,\sum_{i=1}^{km}f(\frac{i}{k})- \sum_{i=1}^{kn}f(\frac{i}{k})\,)
\\\\
\text{Lefthand} \,=& \lim_{k\rightarrow\infty} \frac{1}{k} \sum_{i=kn}^{km-1}f(\frac{i}{k})\\
=&\lim_{k\rightarrow\infty} \frac{1}{k} (\,\sum_{i=1}^{km-1}f(\frac{i}{k})- \sum_{i=1}^{kn-1}f(\frac{i}{k})\,)\\
=&\lim_{k\rightarrow\infty} \frac{1}{k} (\,\sum_{i=1}^{km}f(\frac{i}{k})-f(m)- \sum_{i=1}^{kn}f(\frac{i}{k})+f(n)\,)\\
=&\lim_{k\rightarrow\infty} \frac{1}{k} (\,\sum_{i=1}^{km}f(\frac{i}{k})- \sum_{i=1}^{kn}f(\frac{i}{k})\,)+\frac{f(n)-f(m)}{k}\\
\end{align*}$$
Both Righthand and Lefthand share the first term $\sum_{i=1}^{kn}f(\frac{i}{k})\,$ but Lefthand has additional $\frac{f(n)-f(m)}{k}$. This means that two are only equal if and only if $\frac{f(n)-f(m)}{k} = 0$.
$$\begin{align*}j \text{ is Finite}\Leftrightarrow& \lim_{k\rightarrow\infty}\frac{j}{k}=0\\
\therefore f(n)-f(m) \text{ is Finite} \Leftrightarrow& \frac{f(n)-f(m)}{k}=0\end{align*}$$
This leads to
$$\begin{align*}
\text{Righthand} =& \text{Lefthand} &\Leftrightarrow&  f(n)-f(m) \text{ is Finite}\\
\lim_{k\rightarrow\infty} \frac{1}{k} \sum_{i=kn+1}^{km}f(\frac{i}{k}) = &\lim_{k\rightarrow\infty} \frac{1}{k} \sum_{i=kn}^{km-1}f(\frac{i}{k}) &\Leftrightarrow& f(n)-f(m) \text{ is Finite}\,\blacksquare\end{align*}$$

Similarly, you can show that Trapezoid Sum will also equal to Righthand and Lefthand Sum under the same condition:

$$\text{Trapezoid Sum}=\text{Righthand Sum}=\text{Lefthand Sum} \Leftrightarrow \text{Difference of Endpoints is Finite} $$

Let's express Trapezoid Sum in terms of Lefthand and Righthand Sums:
$$\begin{align*} \text{Trapezoid }=&\lim_{k\rightarrow\infty}\frac{1}{k}\sum_{i=kn+1}^{km}\frac{f(\frac{i-1}{k})+f(\frac{i}{k})}{2}\\
=&\lim_{k\rightarrow\infty}\frac{1}{2k}\sum_{i=kn+1}^{km}( f(\frac{i-1}{k})+f(\frac{i}{k}) )\\
=&\lim_{k\rightarrow\infty}\frac{1}{2k}(\sum_{i=kn+1}^{km}\frac{i-1}{k}+\sum_{i=kn+1}^{km}f(\frac{i}{k}) )\\
=&\lim_{k\rightarrow\infty}\frac{1}{2k}(\sum_{i=kn}^{km-1}f(\frac{i}{k})+\sum_{i=kn+1}^{km}f(\frac{i}{k}) \\
=& \frac{1}{2}( \lim_{k\rightarrow\infty}\frac{1}{k}\sum_{i=kn}^{km-1}f(\frac{i}{k}) + \lim_{k\rightarrow\infty}\frac{1}{k}\sum_{i=kn+1}^{km}f(\frac{i}{k} )\, )\\ =&\frac{1}{2}(\text{Lefthand }+ \text{Righthand}) \end{align*}$$
Given that $f(n)-f(m) \text{ is Finite}$ and without loss of generality between Righthand and Lefthand, we reach that
$$\begin{align*}
\text{Trapezoid } = & \frac{1}{2}(\text{Righthand} + \text{Righthand})\\
=& Righthand \\ \end{align*}\\ \therefore\text{Trapezoid}=\text{Righthand}=\text{Lefthand}, f(n)-f(m) \text{ is Finite} \,\blacksquare$$

Finally, we should show that two formulas for Riemann Sum, $\lim_{k\rightarrow \infty}\frac{1}{k}\sum^{km}_{i=kn+1}f(\frac{i}{k})$ and $ \lim_{k\rightarrow \infty}\frac{m-n}{k}\sum^k_{i=1}f(n+i\frac{m-n}{k})$, equal to the same sum.
This will involve showing that both formulas had equivalent limits and showing there exists a bijection between each terms of Summations in both formulas.
This proof will be left to the readers as exercise, but it could be left as a postulate as well. Visualizing both formulas as $k$ approaches infinity will make the statement more obvious.
Graphics visualizing modified Riemann Summation Formula. Rectangles of $\frac 1k$ intervals are drawn to approximate area of the Curve.  Graphics visualizing classic Riemann Summation Formula. To approximate the curve, $k$ number of rectangles are drawn. 


Conclusion

To sum it all up, we explored two main ideas: Summation with Non-Unit Increments and Simplified Riemann Summation Formula. 
By modifying some terms, we can change Increment value of Summation to a Harmonic Fraction.
$$\sum_{i = kn}^{km}a_{\frac ik}, k \in \mathbb{N}$$
By using Increment Manipulation, we can write a Riemann Sum Formula that is much simpler and easier to deal with.
$$\int _n ^m f(x) dx = \lim_{k\rightarrow \infty}\sum^{km}_{i=kn+1}\frac{1}{k}f(\frac{i}{k})$$
Hopefully this was a concept of Increment Manipulation was interesting to you and I hope you will find other applications for it as well.

Comments

Post a Comment

Popular posts from this blog

Large Polynomial Series using Matrices (Calculating Bernoulli's Number with Pascal Matrix)

Polynomial Series can be easily solved using Power Series Formulas for each term in the polynomial. However, this can be frustrating since not every Power Formula are intuitive to memorize. We would like to find a more elegant and easier-to-recall formula for computing a Polynomial Series. This can be done using matrices. Notations and Equations We will borrow the notations and simple equations from Sequence Curve articles . There, we have extended a series to be continuous through the following identity: $$\sum_{i=m}^n f(i) = \int_{m-1}^nȢ\{f(x)\}dx $$ The $Ȣ\{f(x)\}$ acts as the rate of change of a series relative to its bounds. $$\frac{d}{dt} \sum_{i=m}^nf(i) = Ȣ\{f(n)\}\frac{dn}{dt} - Ȣ\{f(m-1)\}\frac{dm}{dt}$$ Letting $t=m=n$, we find $$\frac{d}{dt} \sum_{i=t}^tf(i) = \frac{d}{dt}f(t)= Ȣ\{f(t)\} - Ȣ\{f(t-1)\} $$ Remebering that $Ȣ$ Transformation is Linear, we can derive a simple identity of $$\frac{d}{dx}f(x+1) = Ȣ\{f(x+1)\} - Ȣ\{f(x)\} = Ȣ\{f(x+1)-f(x)\}$$ This will be use

Vector Plane Rotation

Vector is a useful tool in maths and in physics that describes both magnitude and direction in a space. Vectors are used to describe concepts where direction matter, such as forces and velocity. For example, two cars can have same speed(scalar) but if one if heading north and the other south, they will have different velocity(vector). Vectors are usually written in terms of their components. Components are magnitude of the vector in one dimension. In 2D space, vector can be represented as coordinate of 2 components, <x,y>, and in 3D space, vector can be represented as coordinate of 3 components, <x, y, z>. Breaking down vectors into their components is extremely useful, especially in physics, because it allows one to break down complicated changes in vector into simpler and easier-to-work-with changes in its components. Take a look at projectile motion, for example. Velocity of an object fired up into the sky at an angle changes both its direction and magnitude. Attem

Partition Counter using Trees, Recursion, Tables, and Algorithm

Partitions are number of ways an integer can be represented as sum of positive integers. We can ask, for example, what is the partition of 5? If we write out every possible combination, $$\begin{align*}  5 &= 1+1+1+1+1 \\  &= 1+1+1+2\\ &= 1+1+3\\ &= 1+4\\ &= 1+2+2\\ &= 2+3\\  &= 5 \end{align*} $$ we can see that partition of 5 is 7. One will immediately notice, however, that this is not the most efficient approach to answering the question: not only does partition grow quickly, attempting to organize and not miss or repeat an algebraic expression becomes messy and impractical. Chapter 1: Partition Tree A cleaner, but still not the best, approach would be to use tree diagrams to represent the partitions of a number. In a Partition Tree of $n$, every path to a terminating node will add up to the number $n$. And also, every child of a node (every nodes below a given parent node) will always be greater than or equal to the parent node in order to not