Sum of Computable Rational Sequences is Computable
Jump to navigation
Jump to search
Theorem
Let $\sequence {x_n}$ and $\sequence {y_n}$ be computable rational sequences.
Then, $\sequence {x_n + y_n}$ is a computable rational sequence.
Proof
By definition of computable rational sequence, there exist total recursive $f_x, g_x, f_y, g_y : \N \to \N$ such that:
- $x_n = \dfrac {k_n} {\map {g_x} n + 1}$
- $y_n = \dfrac {\ell_n} {\map {g_y} n + 1}$
where:
- $\map {f_x} n$ codes the integer $k_n$
- $\map {f_y} n$ codes the integer $\ell_n$
We define:
- $\map f n = \paren {\map {g_y} n + 1}_\Z \times_\Z \map {f_x} n +_\Z \paren {\map {g_x} n + 1}_\Z \times_\Z \map {f_y} n$
- $\map g n = \map {g_x} n \times \map {g_y} n + \map {g_x} n + \map {g_y} n$
which are both total recursive by:
- Code Number for Non-Negative Integer is Primitive Recursive
- Multiplication of Integers is Primitive Recursive
- Addition of Integers is Primitive Recursive
- Multiplication is Primitive Recursive
- Addition is Primitive Recursive
Thus, we have:
\(\ds \frac {p_n} {\map g n + 1}\) | \(=\) | \(\ds \frac {\paren {\map {g_y} n + 1} k_n + \paren {\map {g_x} n + 1} \times \ell_n} {\map {g_x} n \map {g_y} n + \map {g_x} n + \map {g_y} n + 1}\) | $\map f n$ codes the integer $p_n$ | |||||||||||
\(\ds \) | \(=\) | \(\ds \frac {\paren {\map {g_y} n + 1} k_n} {\paren {\map {g_x} n + 1} \paren {\map {g_y} n + 1} } + \frac {\paren {\map {g_x} n + 1} \ell_n} {\paren {\map {g_x} n + 1} \paren {\map {g_y} n + 1} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac {k_n} {\map {g_x} n + 1} + \frac {\ell_n} {\map {g_y} n + 1}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds x_n + y_n\) |
$\blacksquare$