The Integer, the Rational and the Real

       
         We're finally done with the number theory questions! Not that I dislike them, but it's nice to see a different type of problems. These will mostly be dealing with functional equations. 

As the name suggests these are equations in which the objective is to find a function that satisfies certain properties (variations include standard fare like finding all functions, etc...). As Terry says in his introduction to this section, these type of problems are interesting since solutions mostly depend on the few properties given. No need for (too many) prerequisites or fancy theorems like we used in some of the previous problems.

This is all good, but there's nothing better than diving right into one of these problems, so without further ado:

This seems like a better format to present the problems instead of just pictures.

          Anyone who's gone this far into the book, even if they've never seen a functional equation before, would agree the strategy given by the hint is pretty sensible. If you can't show it works for integers, you're not going to be able to show it for reals. 

For this first case, the induction flag is strong, so let's see if it works. Let $x\in \mathbb{N}$; we want to show that $f(x) =1+x$. 

The base case is given so no need to worry about that. Assume it's true for $k$: $f(k) =1+k$. Then:

$f(k+1) = f\left( k+0+1 \right) = f(k) +f(0) = 1+k+ 1$

Thus, by induction, it works for natural numbers; solid start!

Integers follow right away by using something I like to call the "particle-antiparticle trick". This is just the standard adding $x$ and subtracting $x$ (or any other inverse operations pairs), but not letting them "annihilate" each other (kind of like how Hawking radiation is supposed to work, hence the terrible name). 
Let $x$ be a positive integer, then:

$f(1) = f(x+(-x)+1) = f(x)+f(-x)$

$2 = 1+x+f(-x)$

\[ \begin{equation*} f(-x) =-x+1 \end{equation*} \]

         With integers done, we go to the rationals. The plan is to link the image(s) of rationals with image(s) of integers so we can get rid of the $f$'s. Dealing with rationals is a bit trickier though, so it's not a bad idea to take a look at some quick examples to get some ideas on how it works. I decided to start on the right side of  the last property given since it's easier to make fractions appear than starting from the left:

$f\left( \dfrac{1}{2} \right) +f\left( \dfrac{1}{2} \right) = f \left( \dfrac{1}{2} + \dfrac{1}{2} + 1 \right) = f(2) = 3$

$f \left( \dfrac{1}{2} \right) = \dfrac{3}{2} = 1 + \dfrac{1}{2}$

This is not a bad start; what about being a bit more ambitious? Let $p \neq 0 \in \mathbb{Z}$:

$2f \left( \dfrac{1}{p} \right) = f \left( \dfrac{2}{p} +1\right) = f\left(\dfrac{2+p}{p} \right)$

We can't do the same "trick" as in the previous example, since we don't have an integer. However, we only added two copies, so maybe more copies could work. Let's try one more example to see if anything becomes clearer:

$3f \left( \dfrac{1}{p} \right) = f \left( \dfrac{1}{p}\right) + f\left(\dfrac{2+p}{p} \right) = f\left( \dfrac{3+p}{p} + 1 \right) = f\left( \dfrac{3+2p}{p} \right)$

The sweet smell of induction is in the air again! It would seem that for $n \in \mathbb{Z}^+$: 

$nf\left( \dfrac{1}{p} \right) = f\left( \dfrac{n+ (n-1)p}{p} \right)$

So as not to make this too long, I'll just write the induction step. Assume the above formula works for some $k$. Then:

$(k+1) f\left( \dfrac{1}{p} \right) = kf\left( \dfrac{1}{p} \right) +f\left( \dfrac{1}{p} \right) = f\left( \dfrac{k+(k-1)p}{p} \right) + f\left( \dfrac{1}{p} \right)$

$= f\left( \dfrac{k+(k-1)p}{p} + \dfrac{1}{p} +1 \right) = f\left( \dfrac{(k+1) + kp}{p} \right)$

This shows our assumption is correct. From this, it directly follows that:

$pf\left( \dfrac{1}{p} \right) = f\left( \dfrac{p+(p-1)p}{p} \right) = f(p) = 1+p$

\[ \begin{equation} \label{(2)} f\left( \dfrac{1}{p} \right) = 1 + \dfrac{1}{p} \end{equation} \]

Just as we hoped! To finish the rationals we'll use the aforementioned particle-antiparticle trick again:

$nf\left( \dfrac{1}{p} \right) = f\left( \dfrac{n+(n-1)p)}{p} \right) = f\left( \dfrac{n}{p} +\color{red}{n-1} \right) = f\left( \dfrac{n}{p} + \color{red}{(n-2) +1} \right)$

$= f\left( \dfrac{n}{p} \right) + f(n-2) = f\left( \dfrac{n}{p} \right) + n-1$

Then, using our result $\eqref{(2)}$ to replace the left hand side:

$n\left( 1 +\dfrac{1}{p} \right) = f \left( \dfrac{n}{p} \right) + n - 1$

$f\left( \dfrac{n}{p} \right) = 1+ \dfrac{n}{p}$

Thus, the formula holds for all rational numbers.

Mothgirls are surprisingly impatient when it comes to lamps real numbers.

         The last step is to show it holds for all real numbers. This is not difficult but it's a rather delicate point since, depending on the level of the reader, the explanation will vary; so I will give two proofs. Do note that any proof for this section will require the only property of $f$ we haven't used so far: $f$ is a continuous function.

First Proof:  This one isn't rigorous but it should be convincing enough. Even if you haven't studied/know too much about continuity, chances are that you have some intuitive idea. 
"A graph that you can draw without lifting your pencil" is the classic one and is enough for our purposes. 

Since we showed that rational numbers follow the formula, if we were to graph them we would see a bunch of points aligned. The only way to draw the complete graph without lifting the pencil would be to fill in the holes of the irrationals exactly where they "should be" to complete the line. Thus, $f(x) = 1+x$ for all $x \in \mathbb{R}$.

Second Proof: Let's be more rigorous this time by using some analysis. Any real number $r$ can be represented by a Cauchy sequence of rational numbers. Let $\{ x_n \}$ be such a sequence:

$\displaystyle \lim_{n \rightarrow \infty} x_n = r$

Since $f$ is continuous:

$\displaystyle \lim_{n \rightarrow \infty} f(x_n) = \lim_{n \rightarrow \infty} f(r)=f(r)$

On the other hand, in the previous section we showed that for all $x_n \in \mathbb{Q}$, $f(x_n) = 1 +x_n$. This implies:

$\displaystyle \lim_{n \rightarrow \infty} f(x_n) = \lim_{n \rightarrow \infty} 1+x_n = 1+r$

Thus:

$f(r) = 1 + r$

Which concludes the proof.

They are also easily pleased.

         There we have it, our first proof of the second chapter of the book. It's been a while since I write one of these posts... School, video games, and just being lazy take a surprisingly big chunk of my time! I had worked out the proof some time ago, but actually writing the post took more time than the previous entries.

The proof itself was rather long, but then again we had to show the same thing for three different sets. I get the feeling there must be a more evident way to show it works for rational numbers, but that I leave for someone else.

This problem is a good example illustrating Terry's point I paraphrased in the intro to this post: The most difficult/interesting part was to manipulate the properties given to be able to show what we needed. A word of caution though: It's extremely easy to get carried away doing algebraic manipulations. It's important to keep the goal in mind at all points so as not to do algebra for the sake of algebra.

That's it! Hopefully I'll gather willpower faster for the next entry!