Symbolic mathematical evaluations
Math is really fun, especially when is done symbolically.
# Overview
This time we're taking a look at some interesting relations and identities for fractions, which will give us an insight of what is really going on, for example, in an infinite sum and how we can analyze it by evaluating it symbolically.
There is an useful and interesting identity for summing two fractions:
$$\frac{a}{b} + \frac{c}{d} = \frac{ad + cb}{bd}$$
The question is: can we extend it to three fractions? What about ten? What about an infinite number of them?
Well, yes, this is possible, and it's actually quite easy to find a general formula to this. To give you a taste how this can be analyzed, let's sum four fractions (using `a` for the numerator and `b` for the denominator, just for illustration, but they can have different values):
$$\frac{a}{b} + \frac{a}{b} + \frac{a}{b} + \frac{a}{b} = \frac{b(b(b(a) + ab) + abb) + abbb}{bbbb}$$
Do you see the pattern? There is a beautiful recursive relation which describes this process.
`\sum_{k=0}^(n)\frac{a_k}{b_k}`
The generic recursive functions for summing an arbitrary number of fractions, turns out to be:
$$
\begin{cases}
g(0) = b_0 \\
g(k) = b_k · g(k-1) \\
--------------- \\
f(0) = a_0 \\
f(k) = b_k · f(k-1) + a_k · g(k-1)
\end{cases}
$$
which leads to our beautiful identity:
`\sum_{k=0}^(n)\frac{a_k}{b_k} = \frac{f(n)}{g(n)}`
For infinite sums, the result is equal with the limit of `n` going to infinity:
`\sum_{k=0}^(\infty)\frac{a_k}{b_k} = \lim_{n to \infty}\frac{f(n)}{g(n)}`
Let's take a concrete example:
`\sum_{k=0}^(\infty)\frac{(-1)^k}{2k+1} = \frac{\pi}{4}`
Taking the numerator and the denominator from the fraction inside the infinite sum, gives us:
`a_k = (-1)^k`
`b_k = 2k+1`
After replacing `a_k` and `b_k` with their actual values in our recursive functions, we have:
$$
\begin{cases}
g(0) = 1 \\
g(k) = (2k+1) · g(k-1) \\
-------------------- \\
f(0) = 1 \\
f(k) = (2k+1) · f(k-1) + (-1)^k · g(k-1)
\end{cases}
$$
The first few values of `f(k)` and `g(k)` functions are:
f(k) g(k)
-----------
The question is: can we extend it to three fractions? What about ten? What about an infinite number of them?
Well, yes, this is possible, and it's actually quite easy to find a general formula to this. To give you a taste how this can be analyzed, let's sum four fractions (using `a` for the numerator and `b` for the denominator, just for illustration, but they can have different values):
$$\frac{a}{b} + \frac{a}{b} + \frac{a}{b} + \frac{a}{b} = \frac{b(b(b(a) + ab) + abb) + abbb}{bbbb}$$
Do you see the pattern? There is a beautiful recursive relation which describes this process.
# Symbolic evaluation of infinite series
Any infinite sum can be evaluated symbolically, using the identity described above. For instance, let's consider the following generic sum:`\sum_{k=0}^(n)\frac{a_k}{b_k}`
The generic recursive functions for summing an arbitrary number of fractions, turns out to be:
$$
\begin{cases}
g(0) = b_0 \\
g(k) = b_k · g(k-1) \\
--------------- \\
f(0) = a_0 \\
f(k) = b_k · f(k-1) + a_k · g(k-1)
\end{cases}
$$
which leads to our beautiful identity:
`\sum_{k=0}^(n)\frac{a_k}{b_k} = \frac{f(n)}{g(n)}`
For infinite sums, the result is equal with the limit of `n` going to infinity:
`\sum_{k=0}^(\infty)\frac{a_k}{b_k} = \lim_{n to \infty}\frac{f(n)}{g(n)}`
Let's take a concrete example:
`\sum_{k=0}^(\infty)\frac{(-1)^k}{2k+1} = \frac{\pi}{4}`
Taking the numerator and the denominator from the fraction inside the infinite sum, gives us:
`a_k = (-1)^k`
`b_k = 2k+1`
After replacing `a_k` and `b_k` with their actual values in our recursive functions, we have:
$$
\begin{cases}
g(0) = 1 \\
g(k) = (2k+1) · g(k-1) \\
-------------------- \\
f(0) = 1 \\
f(k) = (2k+1) · f(k-1) + (-1)^k · g(k-1)
\end{cases}
$$
The first few values of `f(k)` and `g(k)` functions are:
f(k) g(k)
-----------
1 1
2 3
13 15
76 105
789 945
7734 10395
2 3
13 15
76 105
789 945
7734 10395
Finishing the example, we can conclude:
`lim_{n to \infty}\frac{f(n)}{g(n)} = \frac{\pi}{4}`
# Symbolic evaluation of continued fractions
Continued fractions are a little bit more tricky to evaluate symbolically, but we still can do it, using just another identity, and that is:
$$\frac{(\frac{a}{b})}{(\frac{c}{d})} = \frac{ad}{bc}$$
For example, let's try to evaluate the following expression:
`\frac{a}{b+\frac{c}{d}}`
We can start by breaking it up into individual parts:
$$
\begin{cases}
x = a \\
y = \frac{b}{1}+\frac{c}{d} = \frac{bd + c}{d}
\end{cases}
$$
\begin{cases}
x = a \\
y = \frac{b}{1}+\frac{c}{d} = \frac{bd + c}{d}
\end{cases}
$$
Joining the parts back together, we get:
`\frac{x}{y} = \frac{a}{\frac{bd+c}{d}} = \frac{ad}{bd + c}`
We did it! But now we might ask if there is a general formula for evaluating an arbitrary number of such fractions in a similar manner.
For instance, we might want to consider the following continued fraction, with the numerator and the denominator defined by some functions `a()` and `b()`:
`\underset{k=0}{\overset{\infty}{\mathbf{K}}}\frac{a(k)}{b(k)}`
By playing just a little bit more with the evaluation of continued fractions, we can see a pattern emerging, from which we can deduce the following two recursive functions:
$$
\begin{cases}
s(0) = 1 \\
s(1) = 0 \\
s(k) = b(k-1) · s(k-1) + a(k-1) · s(k-2) \\
--------------------- \\
t(0) = 0 \\
t(1) = 1 \\
t(k) = b(k-1) · t(k-1) + a(k-1) · t(k-2)
\end{cases}
$$
The result for our continued fraction is simply:
`\underset{k=0}{\overset{\infty}{\mathbf{K}}}\frac{a(k)}{b(k)} = \lim_{n to \infty}\frac{s(n)}{t(n)`
Now let's take a concrete example:
`\mathbf{K}\frac{1}{1} = φ-1 = 0.618033988749...`
From which we define the numerator as `a(k)` and the denominator as `b(k)`:
`a(k) = 1`
`b(k) = 1`
If we now evaluate our recursive functions, `s(k)` and `t(k)`, we get the following results:
s(k) t(k)
----------
1 0
0 1
1 1
1 2
2 3
3 5
5 8
8 13
13 21
21 34
34 55
I know what you think: "those are the Fibonacci numbers", and you are totally right. The ratio between two consecutive Fibonacci numbers goes to `φ-1` as we look at larger and larger values.
In other words:
`lim_{n to \infty}\frac{s(n)}{t(n)} = φ-1`
We can define the method recursively as:
`w(1) = 1`
`w(k) = \frac{1}{n} * (w(k-1)*(n-1) + \frac{x}{w(k - 1)^(n-1)})`
where `x` is the base number and `n` is the nth root we are trying to calculate.
For example, in finding the `\sqrt(5)`, we have:
`x = 5`
`n = 2`
Using the symbolic rule for the summation of fractions, we can approximate the `sqrt(5)` with fractions:
w(k)
-------------------
1 / 1
6 / 2
56 / 24
6016 / 2688
72318976 / 32342016
For example, let's consider the following recursive function:
`f(0) = 1`
`f(n) = \frac{f(n-1)}{n}`
and the following identity:
`\sum_{n=0}^(\infty)f(n) = e`
Now, how can we prove that the sum does actually converge to `e`? Well, this is an easy case: we can evaluate rationally each value returned by `f(n)`, of which the first terms are:
f(n)
------
1 / 1
1 / 1
1 / 2
1 / 6
1 / 24
1 / 120
If you recognize the denominators, they are the factorial numbers, which give us an insight of what the sum really is:
`\sum_{n=0}^(\infty)\frac{1}{n!}`
which does indeed converge to `e`.
An easy exercise is to find to which value does the following sum converges to:
`g(0) = 1`
`g(n) = g(n-1)*2n`
`\sum_{n=0}^(\infty)\frac{1}{g(n)} = ?`
\begin{cases}
s(0) = 1 \\
s(1) = 0 \\
s(k) = b(k-1) · s(k-1) + a(k-1) · s(k-2) \\
--------------------- \\
t(0) = 0 \\
t(1) = 1 \\
t(k) = b(k-1) · t(k-1) + a(k-1) · t(k-2)
\end{cases}
$$
The result for our continued fraction is simply:
`\underset{k=0}{\overset{\infty}{\mathbf{K}}}\frac{a(k)}{b(k)} = \lim_{n to \infty}\frac{s(n)}{t(n)`
Now let's take a concrete example:
`\mathbf{K}\frac{1}{1} = φ-1 = 0.618033988749...`
From which we define the numerator as `a(k)` and the denominator as `b(k)`:
`a(k) = 1`
`b(k) = 1`
If we now evaluate our recursive functions, `s(k)` and `t(k)`, we get the following results:
s(k) t(k)
----------
1 0
0 1
1 1
1 2
2 3
3 5
5 8
8 13
13 21
21 34
34 55
I know what you think: "those are the Fibonacci numbers", and you are totally right. The ratio between two consecutive Fibonacci numbers goes to `φ-1` as we look at larger and larger values.
In other words:
`lim_{n to \infty}\frac{s(n)}{t(n)} = φ-1`
# Symbolic evaluation of Newton's method
An important and interesting method in mathematics is Newton's method, which finds the positive nth root of a positive number.We can define the method recursively as:
`w(1) = 1`
`w(k) = \frac{1}{n} * (w(k-1)*(n-1) + \frac{x}{w(k - 1)^(n-1)})`
where `x` is the base number and `n` is the nth root we are trying to calculate.
For example, in finding the `\sqrt(5)`, we have:
`x = 5`
`n = 2`
Using the symbolic rule for the summation of fractions, we can approximate the `sqrt(5)` with fractions:
w(k)
-------------------
1 / 1
6 / 2
56 / 24
6016 / 2688
72318976 / 32342016
# Numerical analysis with symbolic evaluation
Besides being entertaining, there is an actual practical benefit in using symbolic evaluation, and most mathematicians use it everyday in their research.For example, let's consider the following recursive function:
`f(0) = 1`
`f(n) = \frac{f(n-1)}{n}`
and the following identity:
`\sum_{n=0}^(\infty)f(n) = e`
Now, how can we prove that the sum does actually converge to `e`? Well, this is an easy case: we can evaluate rationally each value returned by `f(n)`, of which the first terms are:
f(n)
------
1 / 1
1 / 1
1 / 2
1 / 6
1 / 24
1 / 120
If you recognize the denominators, they are the factorial numbers, which give us an insight of what the sum really is:
`\sum_{n=0}^(\infty)\frac{1}{n!}`
which does indeed converge to `e`.
# Exercise
An easy exercise is to find to which value does the following sum converges to:`g(0) = 1`
`g(n) = g(n-1)*2n`
`\sum_{n=0}^(\infty)\frac{1}{g(n)} = ?`
Comments
Post a Comment