Proof by Induction Example

Proof by induction is a powerful, accepted tool for producing not only mathematical proofs but also proofs of algorithms in computer science and other fields as well.

The concept of proof by induction, is generally described as being a three step process:

1. Prove a base case (in many cases we call this $P(1)$).
2. Assume that the $k$th case is true (we call this $P(k)$).
3. Show that the $k+1$th case is true (we call this $P(k+1)$).

As can be seen $P(1) \rightarrow P(2)$, since our base case has been established at $P(1)$ and we have shown that for our $k+1$th case, when $k = 1$ (i.e. $P(2)$) our proposition stands. This can be further extended to show that $P(2) \rightarrow P(3) \rightarrow ... \rightarrow P(n)$.

So, in less-mathematical terms, proof by induction is as simple as proving some proposition is true for some starting value, and then verifying that it is true for the next one, and the next one, continuing on as far as it needs to or, in other words, to the $n$th value.

The following is a simple, somewhat standard example.

Problem

$\forall n \in \mathbb{N}$, prove that: $$\sum_{i = 1}^{n} i = \frac{n \left( n + 1 \right)}{2}$$

(This is saying that if we sum up all the numbers from one to $n$, that sum should equivalently be calculable by $\frac{n \left( n + 1 \right)}{2}$)

Proof

 Before we start the proof, it's useful to...
$$\text{let } P(n) =  \sum_{i = 1}^{n} i$$

Now...

Proof by Induction

Step 1: Prove base-case, $P(1)$:

So, the sum of all number from one to one is:
$$P(1) = \sum_{i = 1}^{1} i = 1$$

Now we verify that our formula works for $n = 1$:
$$\frac{n \left(n + 1 \right)}{2} = \frac{1 \left(1 + 1 \right)}{2} = \frac{2}{2} = 1$$

It checks!

Step 2: Assume that $P(k)$ is true:

So, here we are assuming that:
$$P(k) = \sum_{i = 1}^{k} i = 1 + 2 + 3 + ... + k = \frac{k \left( k + 1 \right)}{2}$$

Step 3: Show that $P(k+1)$ is consistent:

So, $P(k+1)$ looks like, (replacing $n$ with $k + 1$):
$$P(k+1) =  \sum_{i = 1}^{k+1} i = 1 + 2 + 3 + ... + k + (k + 1) = \frac{\left( k + 1 \right) \left[ \left( k + 1 \right) + 1 \right]}{2}$$

Noticing that $1 + 2 + 3 + ... + k$ is the same as $P(k)$ from Step 2:
$$\frac{k \left( k + 1 \right)}{2} + \left( k + 1 \right) = \frac{\left( k + 1 \right) \left[ \left( k + 1 \right) + 1 \right]}{2}$$

Multiplying both sides by $2$:
$$k \left( k + 1 \right) + 2\left( k + 1 \right) = \left( k + 1 \right) \left[ \left( k + 1 \right) + 1 \right]$$

Distribute $k$ and $2$ on the left, add the $1$s on the right:
$$k^2 + k + 2k + 2 = \left( k + 1 \right) \left( k + 2 \right)$$

FOIL the right:
$$k^2 + k + 2k + 2 = k^2 + 2k + k + 2 \text{      $\square$}$$

It's really as easy as that!

Simple Partial Differential Equations Example

I am really enjoying my current partial differential equations class, so I thought I'd share an example problem. Note that this is probably one of the simplest problems in partial DE.

Problem

$$\begin{equation}   \text{(1)    } k^2 \frac{\partial^2 U}{\partial t^2} = \frac{\partial^2 U}{\partial x^2} \end{equation}$$
$$\begin{equation}   \text{(2)    } U \left( 0, t \right) = 0 \end{equation}$$
$$\begin{equation}   \text{(3)    } U \left( L, t \right) = 0 \end{equation}$$
$$\begin{equation}   \text{(4)    } U \left( x, 0 \right) = 0 \end{equation}$$
$$\begin{equation}   \text{(5)    } \frac{\partial U}{\partial t} \left( x, 0 \right) = f \left( x \right) \end{equation}$$

Solution

We are looking for a solution of the form:
$$U = XT$$
Where $X$ is a function of $x$ and $T$ is a function of $t$.

Translating (1) to match the expected solution, we get:
$$k^2 XT^{\prime\prime} = X^{\prime\prime} T$$

Dividing each side by $XT$:
$$k^2 \frac{T^{\prime\prime}}{T} = \frac{X^{\prime\prime}}{X}$$

Since we have a function of only $T$ on the left and only $X$ on the right, we know that these are equal to a constant.
$$k^2 \frac{T^{\prime\prime}}{T} = \frac{X^{\prime\prime}}{X} = constant = \left\{\begin{array}{lr}   0 \\   -\lambda^2 \\   \lambda^2 \end{array}   \right.$$

The notation above says that the constant can either be $0$, some negative number (as forced to be negative by $-\lambda^2$) or some positive number (forced by $\lambda^2$).

Case $constant = 0$:

Finding $X$:
$$\frac{X^{\prime\prime}}{X} = 0 \Rightarrow X^{\prime\prime} = 0$$

Integrating both sides:
$$X^{\prime} = A$$
Where $A$ is an arbitrary constant.

Integrating again:
$$X = A x + B$$
Where $B$ is an arbitrary constant.

Finding $T$:
$$\frac{k^2 T^{\prime\prime}}{T} = 0 \Rightarrow T^{\prime\prime} = 0$$

Integrating both sides:
$$T^{\prime} = C$$
Where $C$ is an arbitrary constant.

Integrating again:
$$T = C t + D$$
Where $D$ is an arbitrary constant.

Since $U = XT$:
$$U = \left(A x + B\right) \left( C t + D \right)$$
Therefore, this satisfies (1).

Looking at (2), we have:
$$U \left( 0, t \right) = 0 \Rightarrow \left(A (0) + B\right) \left( C t + D \right) = 0 \Rightarrow B \left( C t + D \right)= 0$$

This implies that $B = 0$, so:
$$U = A x \left( C t + D \right) = x \left( C t + D \right)$$
satisfies (1) and (2); note that the constant $A$ was absorbed into the other constants (since they are, after all, just arbitrary constants).

Looking at (3), we have:
$$U \left( L, t \right) = 0 \Rightarrow L \left( C t + D \right) = 0$$

To make this true, we can't change the value of $L$ because it is a constraint, so the only option is to make $C = D = 0$.

So,
$$U = 0$$
This, however, is an uninteresting solution for $U$. So, we examine the next possible constant.

Case $constant = -\lambda^2$:

Finding $X$:
$$\frac{X^{\prime\prime}}{X} = -\lambda^2$$

Multiply both sides by $X$:
$$X^{\prime\prime} = -\lambda^2 X$$

Using methods from differential equations (DE), we know that we can solve this by subbing $\alpha^2$ in for $X^{\prime\prime}$ and $1$ in for $X$:
$$\alpha^2 = -\lambda^2$$

Taking the square root of both sides we get:
$$\alpha = \pm \lambda i$$

From DE we know that this fits the form $\alpha = b \pm c i$, where the answer the the DE is:
$$X = e^{bx} \left[ A \cos \left( c x \right) + B \sin \left( c x \right)\right]$$
Where $A$ and $B$ are arbitrary constants.

Therefore:
$$X = e^{0x} \left[ A \cos \left( \lambda x \right) + B \sin \left( \lambda x \right)\right] = \left[ A \cos \left( \lambda x \right) + B \sin \left( \lambda x \right)\right]$$

Finding $T$:

$$k^2 \frac{T^{\prime\prime}}{T} = -\lambda^2$$

Multiply both sides by $\frac{T}{k^2}$:
$$T^{\prime\prime} = -\frac{\lambda^2}{k^2} T$$

Using methods from differential equations (DE), we know that we can solve this by subbing $\beta^2$ in for $T^{\prime\prime}$ and $1$ in for $T$:
$$\beta^2 = -\frac{\lambda^2}{k^2}$$

Taking the square root of both sides we get:
$$\beta = \pm \frac{\lambda}{k} i$$

From DE we know that this also fits the form $\beta = b \pm c i$, where the answer the the DE is:
$$T = e^{bt} \left[ C \cos \left( c t \right) + D \sin \left( c t \right)\right]$$
Where $C$ and $D$ are arbitrary constants (not necessarily the same as $A$ and $B$).

Therefore:
$$T = e^{0t} \left[ C \cos \left( \frac{\lambda}{k} t \right) + D \sin \left( \frac{\lambda}{k} t \right)\right] = \left[ C \cos \left( \frac{\lambda}{k} t \right) + D \sin \left( \frac{\lambda}{k} t \right)\right]$$

Since $U = XT$:
$$U = \left[ A \cos \left( \lambda x \right) + B \sin \left( \lambda x \right)\right] \left[ C \cos \left( \frac{\lambda}{k} t \right) + D \sin \left( \frac{\lambda}{k} t \right)\right]$$
Therefore, this satisfies (1).

Looking at (2), we have:
$$U \left( 0, t \right) = 0 \Rightarrow \left[ A \cos \left( 0 \right) + B \sin \left( 0 \right)\right] \left[ C \cos \left( \frac{\lambda}{k} t \right) + D \sin \left( \frac{\lambda}{k} t \right)\right] = 0$$

$\cos \left( 0 \right) = 1$ and $\sin \left( 0 \right) = 0$, so,
$$A \left[ C \cos \left( \frac{\lambda}{k} t \right) + D \sin \left( \frac{\lambda}{k} t \right)\right] = 0$$

This implies that $A = 0$, so:
$$U = \sin \left( \lambda x \right) \left[ C \cos \left( \frac{\lambda}{k} t \right) + D \sin \left( \frac{\lambda}{k} t \right)\right]$$   
satisfies (1) and (2); note that the constant $B$ was absorbed into the other constants (since they are, after all, just arbitrary constants).

Looking at (3), we have:
$$U \left( L, t \right) = 0 \Rightarrow \sin \left( \lambda L \right) \left[ C \cos \left( \frac{\lambda}{k} t \right) + D \sin \left( \frac{\lambda}{k} t \right)\right] = 0$$

So, we need to pick a value for $\lambda$ that causes the above expression to always be zero. We find that there are an infinite number of them (everywhere $\sin \left( n \pi \right)$ where n is a natural number (better suited to match the solution than an integer). So, because of this, we find that:
$$\lambda = \frac{n \pi}{L},\, \forall n \in \mathbb{N}$$

So, subbing in for $\lambda$, we have:
$$U = \sin \left( \frac{n \pi x}{L} \right) \left[ C \cos \left( \frac{n \pi}{L k} t \right) + D \sin \left( \frac{n \pi}{L k} t \right)\right]$$
Which satisfies (1), (2) and (3).

Looking at (4), we have:
$$U \left( x, 0 \right) = 0 \Rightarrow \sin \left( \frac{n \pi x}{L} \right) \left[ C \cos \left( 0 \right) + D \sin \left( 0 \right)\right] = 0$$

$\cos \left( 0 \right) = 1$ and $\sin \left( 0 \right) = 0$, so,
$$U \left( x, 0 \right) = 0 \Rightarrow \sin \left( \frac{n \pi x}{L} \right) \left( C \right) = 0$$

This implies that $C = 0$, so,
$$U = \sin \left( \frac{n \pi x}{L} \right) \left( D \right) \sin \left( \frac{n \pi}{L k} t \right)$$
Satisfies (1), (2), (3) and (4).

Since constraint (5) is non-zero, I will evaluate it lastly. For now, I claim that:
$$U = \sum_{n = 1}^{\infty} D_n \sin \left( \frac{n \pi x}{L} \right) \sin \left( \frac{n \pi}{L k} t \right)$$
$\forall n \in \mathbb{N}$, also satisfies (1), (2), (3), and (4). This claim is justified because, as show above, constraint (3) is satisfied for all values of $n$. So, for whatever $n$ I pick from the natural numbers ($1,2,3...$, $\mathbb{N}$) the resulting $U$ will also be an answer. So, summing together the infinite answers for $U$ still meets the problem's criteria. $D$ became $D_n$ because $D$ is not necessarily the same thing for any $n$ value.

So, considering constraint (5), we need to first find $\frac{\partial U}{\partial t}$:
$$\frac{\partial U}{\partial t} = \sum_{n = 1}^{\infty} D_n \sin \left( \frac{n \pi x}{L} \right) \left( \frac{n \pi}{L k} \right) \cos \left( \frac{n \pi}{L k} t \right)$$

Looking at the actual constraint, (5):
$$\frac{\partial U}{\partial t} \left( x, 0 \right) = f \left( x \right) \Rightarrow \sum_{n = 1}^{\infty} D_n \sin \left( \frac{n \pi x}{L} \right) \left( \frac{n \pi}{L k} \right) \cos \left( 0 \right) = f \left( x \right)$$

Since, $\cos \left( 0 \right) = 1$:
$$f \left( x \right) = \sum_{n = 1}^{\infty} D_n \sin \left( \frac{n \pi x}{L} \right) \left( \frac{n \pi}{L k} \right)$$

By the Fourier sine series, we know that the coefficients are given by:
$$D_n \left( \frac{n \pi}{L k} \right) = \frac{2}{L} \int_0^L f \left( x \right) \sin \left( \frac{n \pi x}{L} \right) dx$$
We include $\left( \frac{n \pi}{L k} \right)$ because it does not match the Fourier series and needs to be divided out.

Solving for the actual coefficients:
$$D_n = \frac{2 k}{n \pi} \int_0^L f \left( x \right) \sin \left( \frac{n \pi x}{L} \right) dx$$

Where our final $U$ is, as above:
$$U = \sum_{n = 1}^{\infty} D_n \sin \left( \frac{n \pi x}{L} \right) \sin \left( \frac{n \pi}{L k} t \right)$$

Now, we could go on to examine the $constant = \lambda^2$ case. However, it ends up just being $0$ (and is therefore redundant). You can use methods like those above to come to this conclusion for yourself.

Nieve Prime Finder in Haskell

To solve a cyber-dojo challenge (implement a function/method that returns the prime factors of a number) I decided to implement a somewhat nieve (but workable) isPrime function in Haskell. Here's the code:

-- Public type-definition
isPrime :: Integer -> Bool

-- Private type-definition
lookForPrimeFrom :: Integer -> Integer -> Bool

isPrime 2 = True
isPrime n
 | n < 2     = False
 | even n    = False
 | otherwise = lookForPrimeFrom n 5

lookForPrimeFrom n i
 | ceiling (sqrt (fromIntegral n))+1 < i   = True
 | (n `mod` i) == 0                        = False
 | otherwise                               = lookForPrimeFrom n (i+2)


This code (to me at least) seems very self-documenting. The more I'm playing around with Haskell, the more I'm enjoying it and seeing its strength as a functional language. I think if I were to map this algorithm into more mathematical notation it would look like:

$$\forall n \in \mathbb{N}$$
$$p \left( n \right) = \left\{ \begin{array}{lr}   0, & n = 1 \\   1, & n = 2 \\   0, & \text{$n$ is even} \\   1, & \nexists m \in \left\{ x \in \mathbb{N} \, | \, 5 \leq x \leq{\sqrt{n}}, \text{$x$ is odd}  \right\}    \end{array} \right.$$

As you can see, this is somewhat nieve; however, the Haskell code really is quite similar to the mathematical notation.

Communication between Python and Ruby Using Sockets

Sockets are a neat and (relatively) simple means of communication between different programs in a client-server relationship. They can also be used when it is necessary to communicate data between languages and speed is not a large issue.

The following code examples are a Python lyric server that I built and a Ruby client. Their full code is available on my github account.

simple_lyric_server.py (some implementation details hidden, see github for more):

import socket

 class LyricServer(object):
    def __init__(self):
        # Details hidden... See github

    def try_get_lyrics(self):
        # Details hidden... See github

    def define_socket(self, port, n_requests=5):
        """
            Used to define the socket object from inputs
        """
        host = socket.gethostname()
        print "Lyric Thief Server: Hostname is %s" % str(host)
        self._socket.bind((host, port))
        self._n_requests = n_requests

    def handle_lyric_requests(self):
        self._socket.listen(self._n_requests)

        while True:
            client, address = self._socket.accept()
            print "Lyric Thief Server: Connected to %s" % str(address)

            self.lyrics = ''
            data = json.loads(client.recv(1024))
            try:
                self.artist, self.song = data['artist'], data['song']
            except KeyError:
                client.send("Invalid JSON passed")
                print "Lyric Thief Server: Invalid JSON Passed"
                client.close()
                return

            self.try_get_lyrics()

            # Try sending the lyrics line-by line

            for line in self.lyrics.split('\n'):
                client.send(line+'\n')

            print "Lyric Thief Server: Sent Lyrics, Closing Connection"
            client.close()

 
if __name__ == '__main__':
    server = LyricServer()
    server.define_socket(915, 5)
    server.handle_lyric_requests() 


So, quickly walking through what the methods do:

• define_socket(self, port, n_requests=5) uses the properties attached to a socket object to construct the server's socket, where port is the port that the server will run on and n_requests specifies the maximum number of requests that the server can handle at once.
• handle_lyric_request(self) tries to lookup (online) the lyrics of the song/artist pair JSON data that is passed in from a client and then send back an appropriate response.

Now looking at ruby_client.rb: 

require 'socket'

host = Socket.gethostname
port = 915

s = TCPSocket.new host, port
s.puts('{ "artist" : "Counting Crows", "song" : "Omaha"}')
lyrics = ""

begin
  while line = s.gets
    lyrics += line
  end
rescue
end 
s.close 

So, this Ruby client is much simpler. Essentially all it's doing is (1) building a new TCPSocket using the host machine and the same port as specified in the Python server, (2) writing a JSON object to the port (a request for the "Counting Crows" song "Omaha"), then it (3) reads in the lyrics and closes the connection.

JavaScript in Rails 3.2

After struggling to get CoffeeScript running correctly in my current Rails app, I decided to try using plain-ol' JavaScript and everything worked like a charm. CoffeeScript is very cool (don't get me wrong), however, setting it up is a painful and poorly documented process that proved (in my case) to be fruitless. Anyhow, I though it might be helpful to document how simple it is to get normal JavaScript working on a Rails app.

Firstly, enter the following line in the view that needs JavaScript code:
    <%= javascript_include_tag "my_js_file" %>

This line ensures that my_js_file.js is included in the current view (note that in the "include tag" the ".js" is omitted).

Secondly,  simply code/add your JavaScript file to /app/assets/javascripts/. It will now be available in your view!

I am somewhat conflicted as to how valuable this modus operandi is (there are a few good articles arguing about the benefits of using CoffeeScript); however, at the current moment it is the best solution I have found. If you know any tips about linking CoffeeScript to Rails, please comment below!