Lesson 07 Mathematical induction.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ This Jupyter notebook<sup>[1]</sup> is part of the Klopper Letures on Discrete Matheamtics and covers *mathematical induction*\n",
    "+ Created by me, Dr Juan H Klopper\n",
    "    + Head of Acute Care Surgery\n",
    "    + Groote Schuur Hospital\n",
    "    + University Cape Town\n",
    "    + <a href=\"mailto:juan.klopper@uct.ac.za\">Email me with your thoughts, comments, suggestions and corrections</a> \n",
    "<a rel=\"license\" href=\"http://creativecommons.org/licenses/by-nc/4.0/\"><img alt=\"Creative Commons Licence\" style=\"border-width:0\" src=\"https://i.creativecommons.org/l/by-nc/4.0/88x31.png\" /></a><br /><span xmlns:dct=\"http://purl.org/dc/terms/\" href=\"http://purl.org/dc/dcmitype/InteractiveResource\" property=\"dct:title\" rel=\"dct:type\">The Klopper Lectures on Discrete Mathematics</span> <span xmlns:cc=\"http://creativecommons.org/ns#\" property=\"cc:attributionName\"></span> study notes is licensed under a <a rel=\"license\" href=\"http://creativecommons.org/licenses/by-nc/4.0/\">Creative Commons Attribution-NonCommercial 4.0 International License</a>.\n",
    "\n",
    "+ [1] Fernando Pérez, Brian E. Granger, IPython: A System for Interactive Scientific Computing, Computing in Science and Engineering, vol. 9, no. 3, pp. 21-29, May/June 2007, doi:10.1109/MCSE.2007.53. URL: http://ipython.org"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<link href='http://fonts.googleapis.com/css?family=Alegreya+Sans:100,300,400,500,700,800,900,100italic,300italic,400italic,500italic,700italic,800italic,900italic' rel='stylesheet' type='text/css'>\n",
       "<link href='http://fonts.googleapis.com/css?family=Arvo:400,700,400italic' rel='stylesheet' type='text/css'>\n",
       "<link href='http://fonts.googleapis.com/css?family=PT+Mono' rel='stylesheet' type='text/css'>\n",
       "<link href='http://fonts.googleapis.com/css?family=Shadows+Into+Light' rel='stylesheet' type='text/css'>\n",
       "<link href='http://fonts.googleapis.com/css?family=Philosopher:400,700,400italic,700italic' rel='stylesheet' type='text/css'>\n",
       "\n",
       "<style>\n",
       "\n",
       "@font-face {\n",
       "    font-family: \"Computer Modern\";\n",
       "    src: url('http://mirrors.ctan.org/fonts/cm-unicode/fonts/otf/cmunss.otf');\n",
       "}\n",
       "\n",
       "#notebook_panel { /* main background */\n",
       "    background: #ddd;\n",
       "    color: #000000;\n",
       "}\n",
       "\n",
       "\n",
       "\n",
       "/* Formatting for header cells */\n",
       ".text_cell_render h1 {\n",
       "    font-family: 'Philosopher', sans-serif;\n",
       "    font-weight: 400;\n",
       "    font-size: 2.2em;\n",
       "    line-height: 100%;\n",
       "    color: rgb(0, 80, 120);\n",
       "    margin-bottom: 0.1em;\n",
       "    margin-top: 0.1em;\n",
       "    display: block;\n",
       "}\t\n",
       ".text_cell_render h2 {\n",
       "    font-family: 'Philosopher', serif;\n",
       "    font-weight: 400;\n",
       "    font-size: 1.9em;\n",
       "    line-height: 100%;\n",
       "    color: rgb(200,100,0);\n",
       "    margin-bottom: 0.1em;\n",
       "    margin-top: 0.1em;\n",
       "    display: block;\n",
       "}\t\n",
       "\n",
       ".text_cell_render h3 {\n",
       "    font-family: 'Philosopher', serif;\n",
       "    margin-top:12px;\n",
       "    margin-bottom: 3px;\n",
       "    font-style: italic;\n",
       "    color: rgb(94,127,192);\n",
       "}\n",
       "\n",
       ".text_cell_render h4 {\n",
       "    font-family: 'Philosopher', serif;\n",
       "}\n",
       "\n",
       ".text_cell_render h5 {\n",
       "    font-family: 'Alegreya Sans', sans-serif;\n",
       "    font-weight: 300;\n",
       "    font-size: 16pt;\n",
       "    color: grey;\n",
       "    font-style: italic;\n",
       "    margin-bottom: .1em;\n",
       "    margin-top: 0.1em;\n",
       "    display: block;\n",
       "}\n",
       "\n",
       ".text_cell_render h6 {\n",
       "    font-family: 'PT Mono', sans-serif;\n",
       "    font-weight: 300;\n",
       "    font-size: 10pt;\n",
       "    color: grey;\n",
       "    margin-bottom: 1px;\n",
       "    margin-top: 1px;\n",
       "}\n",
       "\n",
       ".CodeMirror{\n",
       "        font-family: \"PT Mono\";\n",
       "        font-size: 100%;\n",
       "}\n",
       "\n",
       "</style>\n",
       "\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.core.display import HTML\n",
    "#css_file = 'numericalmoocstyle.css'\n",
    "#css_file = \"custom.css\"\n",
    "css_file = 'style.css'\n",
    "HTML(open(css_file, 'r').read())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import sympy as sym"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "sym.init_printing(use_latex = \"mathjax\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Mathematical induction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## In this lesson"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Follow these links\n",
    "- [Introduction](#Introduction)\n",
    "- [Stepping through proof by mathematical induction](#Stepping-through-proof-by-mathematical-induction)\n",
    "    - [Example 1](#Example-1)\n",
    "    - [Example 2](#Example-2)\n",
    "    - [Example 3](#Example-3)\n",
    "- [Proof by strong mathematical induction](#Proof-by-strong-mathematical-induction)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Even in single varaible calculus you might have come across the method of proof called **Proof by Mathematical Induction**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We introduce mathematical induction in this way.  Let $ {P} { \\left( n \\right) } $ be a statement which, for all natural numbers, $ n \\in \\mathbb{N} $, may be either *true* or *false*.  To prove that $ {P} { \\left( n \\right) } $ is *true* for all values of $ n $, it is sufficeint to prove\n",
    "- $ {P} { \\left( 1 \\right) } $ is *true*\n",
    "- $ \\forall k \\ge 1, \\quad {P} { \\left( k \\right) } \\Rightarrow {P} { \\left( k+1 \\right) } $"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You might often come across problems where the first few values of $ k $ don't obey the proof.  You will find that there is a value for $ k $ after whicg the rule does apply.  So, do accomodate this we modify the above to a more general form.<p/>\n",
    "So, to prove $ {P} { \\left( n \\right) } $ is *true* for all integers, $ n \\ge {n}_{0} $, where $ {n}_{0} $ is a fixed positive integer, determined beforehand, it is sufficient to prove that\n",
    "- $ {P} { \\left( {n}_{0} \\right) } $ is *true*\n",
    "- $ \\forall k \\ge {n}_{0}, \\quad {P} { \\left( k \\right) } \\Rightarrow {P} { \\left( k+1 \\right) } $"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "[Back to the top](#In-this-lesson)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Stepping through proof by mathematical induction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- The first step is called the **basis of induction** and involves proving that $ {P}{ \\left( {n}_{0} \\right) } $ is *true*\n",
    "- The next step is the **induction hypothesis** where we assume that $ {P}{ \\left( k \\right) } $ is *true*\n",
    "- In the **indictive step** we show that $ {P}{ \\left( k + 1 \\right) } $ is *true* based on the induction hypothesis"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Example:  Show that the **conjecture** $ S\\left( n \\right)=\\frac { n\\left( n+1 \\right)  }{ 2 }  $ is *true* for $ S\\left( n \\right) =\\sum _{ i=1 }^{ n }{ i }  $."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For small values of $ n $ we see that the conjecture holds\n",
    "$$ S \\left( 1 \\right) = \\frac{1 \\left( 1 + 1 \\right)}{2} = 1 \\\\ S \\left( 2 \\right) = \\frac{2 \\left( 2 + 1 \\right)}{2} = 3 $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We use $ S \\left( 1 \\right) $ as our **basis of induction**.<p/>\n",
    "For our **induction hypothesis** we state that $ S \\left( k \\right) = \\frac{k \\left( k + 1 \\right)}{2}, \\quad k \\ge 1 $.<p/>\n",
    "For our **induction step** we note that $ S\\left( k+1 \\right) =1+2+3+\\dots +k+\\left( k+1 \\right) \\\\ S\\left( k+1 \\right) =S\\left( k \\right) +\\left( k+1 \\right) \\\\ S\\left( k+1 \\right) =\\frac { k\\left( k+1 \\right)  }{ 2 } +\\left( k+1 \\right) \\\\ S\\left( k+1 \\right) =\\frac { k\\left( k+1 \\right) +2\\left( k+1 \\right)  }{ 2 } \\\\ S\\left( k+1 \\right) =\\frac { \\left( k+1 \\right) \\left( k+2 \\right)  }{ 2 } \\\\ S\\left( k+1 \\right) =\\frac { \\left( k+1 \\right) \\left[ \\left( k+1 \\right) +1 \\right]  }{ 2 }  $<p/>\n",
    "Note that we have shown that $ S \\left( k \\right) \\Rightarrow S \\left( k + 1 \\right) $.  If you substitute $ k + 1 $ for $ k $ in $ S \\left( k \\right) $ you get $ S\\left( k+1 \\right) =\\frac { \\left( k+1 \\right) \\left[ \\left( k+1 \\right) +1 \\right]  }{ 2 }  $."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So we know that $ S \\left( 1 \\right) $ is *true* and since $ k $ is any value, it might as well be $ 1 $ which gives us $ S \\left( 2 \\right) $ and so on and so on, i.e. we have proven our conjecture by mathematical induction."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Back to the top](#In-this-lesson)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's prove another conjecture which states that $ S\\left( n \\right) ={ \\left( \\sum _{ i=1 }^{ n }{ i }  \\right)  }^{ 2 } $ is *true* for $ S\\left( n \\right) =\\sum _{ i=1 }^{ n }{ { i }^{ 3 } }  $."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have already seen that $ S\\left( n \\right)=\\frac { n\\left( n+1 \\right)  }{ 2 }  $ is *true* for $ S\\left( n \\right) = \\sum _{ i=1 }^{ n }{ i }  $, so our conjecture really is $ S\\left( n \\right) ={ \\left[ \\frac { n\\left( n+1 \\right)  }{ 2 }  \\right]  }^{ 2 } $ for $ S \\left( n \\right) = {1}^{3} + {2}^{3} + {3}^{3} + \\dots + {n}^{3}  $."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can set up a quick python™ function to check the first few values for our conjecture."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def sqrs(n): # Define a function that takes a single argument\n",
    "    total = 0 # Initialize a computer variable called total\n",
    "    for i in range(1, n+1): # Run trhough a loop to include integers 1 to n\n",
    "        total = total + i**3 # Update total by adding cube of loop value\n",
    "    return total # Return the total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'sqrs' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-1-a4073be204b7>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;31m# Callin the function and passing the value 1 to it\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0msqrs\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m: name 'sqrs' is not defined"
     ]
    }
   ],
   "source": [
    "# Callin the function and passing the value 1 to it\n",
    "sqrs(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$9$$"
      ],
      "text/plain": [
       "9"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sqrs(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$36$$"
      ],
      "text/plain": [
       "36"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sqrs(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$100$$"
      ],
      "text/plain": [
       "100"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sqrs(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Indeed we note that we are squaring the sum of the integers (as in the first example), so we know that $ S \\left( 1 \\right) $ is *true*.  We have our **basis of induction**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we assume $ S \\left( k \\right) = { \\left[ \\frac{k \\left( k + 1 \\right)}{2} \\right]}^{2} $ is *true* for our **induction hypothesis**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our **induction step** is then\n",
    "$$ S\\left( k \\right) ={ \\left[ \\frac { k\\left( k+1 \\right)  }{ 2 }  \\right]  }^{ 2 }\\\\ S\\left( k+1 \\right) ={ 1 }^{ 3 }+{ 2 }^{ 3 }+{ 3 }^{ 3 }+{ k }^{ 3 }+{ \\left( k+1 \\right)  }^{ 3 }\\\\ S\\left( k+1 \\right) =S\\left( k \\right) +{ \\left( k+1 \\right)  }^{ 3 }\\\\ S\\left( k+1 \\right) ={ \\left[ \\frac { k\\left( k+1 \\right)  }{ 2 }  \\right]  }^{ 2 }+{ \\left( k+1 \\right)  }^{ 3 }\\\\ S\\left( k+1 \\right) =\\frac { { \\left[ k\\left( k+1 \\right)  \\right]  }^{ 2 }+4{ \\left( k+1 \\right)  }^{ 3 } }{ 4 } =\\frac { { k }^{ 2 }{ \\left( k+1 \\right)  }^{ 2 }+4{ \\left( k+1 \\right)  }^{ 3 } }{ 4 } \\\\ S\\left( k+1 \\right) =\\frac { { \\left( k+1 \\right)  }^{ 2 }{ \\left[ { k }^{ 2 }+4\\left( k+1 \\right)  \\right]  } }{ 4 } =\\frac { { \\left( k+1 \\right)  }^{ 2 }\\left( { k }^{ 2 }+4k+4 \\right)  }{ 4 } =\\frac { { \\left( k+1 \\right)  }^{ 2 }{ \\left( k+2 \\right)  }^{ 2 } }{ { 2 }^{ 2 } } ={ \\left[ \\frac { \\left( k+1 \\right) \\left[ \\left( k+1 \\right) +1 \\right]  }{ 2 }  \\right]  }^{ 2 } $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Again, we know it held for $ 1 $ and we have shown that $ S \\left( k \\right) \\Rightarrow S \\left( k + 1 \\right) $."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Back to the top](#In-this-lesson)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Prove the conjecture that $ S\\left( n \\right) ={ n }^{ 2 } $ is *true* for $ S\\left( n \\right) =1+3+5+7+\\dots +\\left( 2n-1 \\right)  $."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can do all the steps in one go."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$ S\\left( 1 \\right) =1\\\\ S\\left( k \\right) =1+3+5+7+\\dots +\\left( 2k-1 \\right) \\\\ S\\left( k+1 \\right) =1+3+5+7+\\dots +\\left[ 2\\left( k+1 \\right) -1 \\right] \\\\ S\\left( k+1 \\right) =1+3+5+7+\\dots +\\left( 2k-1 \\right) +\\left( 2k+2-1 \\right) \\\\ S\\left( k+1 \\right) =1+3+5+7+\\dots +\\left( 2k-1 \\right) +\\left( 2k+1 \\right) \\\\ S\\left( k+1 \\right) =S\\left( k \\right) +\\left( 2k+1 \\right) \\\\ S\\left( k+1 \\right) ={ k }^{ 2 }+2k+1\\\\ S\\left( k+1 \\right) ={ \\left( k+1 \\right)  }^{ 2 }\\\\ \\therefore \\quad S\\left( k \\right) \\Rightarrow S\\left( k+1 \\right)  $"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Back to the top](#In-this-lesson)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Proof by strong mathematical induction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This method of proof build from what have learnt above.  We let $ {P}{ \\left( n \\right) }$ be a statement that may be *true* or *false* for each integer, $ n $.  However, $ {P}{ \\left( n \\right) } $ is *true* for all positive integers if there is an integer $ q \\ge 1 $ such that\n",
    "- $ {P}{ \\left( 1 \\right)}, {P}{ \\left( 2 \\right)}, \\dots {P}{ \\left( q \\right)} $ are all *true*\n",
    "- When $ k \\ge q $, the assumption that $ {P} { \\left( i \\right) } $ is *true* for all integers $ 1 \\le i \\le k $ implies that $ {P} { \\left( k + 1 \\right) } $ is *true*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The steps involved for the proof by strong mathematical induction are\n",
    "- By the **basis of strong induction** show that $ {P}{ \\left( 1 \\right)}, {P}{ \\left( 2 \\right)}, \\dots {P}{ \\left( q \\right)} $ are all *true*\n",
    "- By the **strong induction hypothesis** assume that $ {P} { \\left( i \\right) } $ is *true* for all integers $ i $ such that $ 1 \\le i \\le k $ where $ k \\ge q $\n",
    "- By the **strong induction step** show that $ {P} { \\left( k + 1 \\right) } $ is *true* on the basis of the **string induction hypothesis**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In order to follow these steps, we must introduce the concept of **recursion**.  We do it like this.  Let $ \\mathbb{N} $ be the set of non-negative integers.  A function from the set $ \\mathbb{N} $ is defined recursively if the value of $ f $ at $ 0 $ is given and for each positive integer the value of $ {f}{ \\left( n \\right) } $ is defined in terms of the values of $ f $ at $ k $ where $ 0 \\le k \\le n $."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Fibonacci sequence is the most famous recursion $ {F}{ \\left( 0 \\right) } = 1= {F}{ \\left( 1 \\right) } \\\\ {F}{ \\left( n + 1 \\right) } = {F}{ \\left( n \\right) } + {F}{ \\left( n - 1 \\right) } $<p/>\n",
    "We have to prove that $ {F}{ \\left( n \\right) } = \\frac { 1 }{ \\sqrt { 5 }  } \\left[ { \\left( \\frac { 1+\\sqrt { 5 }  }{ 2 }  \\right)  }^{ n+1 }-{ \\left( \\frac { 1-\\sqrt { 5 }  }{ 2 }  \\right)  }^{ n+1 } \\right], \\quad \\forall n \\in \\mathbb{Z}^{+} $."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can write a python™ function to check the first values for our **basis of strong induction**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def fib(n):\n",
    "    return (1 / sym.sqrt(5)) * ((((1 + sym.sqrt(5)) / (2))**(n + 1)) - (((1 - sym.sqrt(5)) / (2))**(n + 1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$1$$"
      ],
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fib(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\frac{\\sqrt{5}}{5} \\left(- \\left(- \\frac{\\sqrt{5}}{2} + \\frac{1}{2}\\right)^{2} + \\left(\\frac{1}{2} + \\frac{\\sqrt{5}}{2}\\right)^{2}\\right)$$"
      ],
      "text/plain": [
       "      ⎛               2              2⎞\n",
       "      ⎜  ⎛    ___    ⎞    ⎛      ___⎞ ⎟\n",
       "  ___ ⎜  ⎜  ╲╱ 5    1⎟    ⎜1   ╲╱ 5 ⎟ ⎟\n",
       "╲╱ 5 ⋅⎜- ⎜- ───── + ─⎟  + ⎜─ + ─────⎟ ⎟\n",
       "      ⎝  ⎝    2     2⎠    ⎝2     2  ⎠ ⎠\n",
       "───────────────────────────────────────\n",
       "                   5                   "
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Since we are using sympy, we will get a mathematical result\n",
    "fib(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$1$$"
      ],
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# We can simplify this\n",
    "fib(1).simplify()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see the Fibonacci number for $ 0 $ to $ 10 $."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 \t 1\n",
      "1 \t 1\n",
      "2 \t 2\n",
      "3 \t 3\n",
      "4 \t 5\n",
      "5 \t 8\n",
      "6 \t 13\n",
      "7 \t 21\n",
      "8 \t 34\n",
      "9 \t 55\n",
      "10 \t 89\n"
     ]
    }
   ],
   "source": [
    "for i in range(0, 11):\n",
    "    print(i, \"\\t\", fib(i).simplify())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For our **strong induction hypothesis** we assume that for $ n \\ge 1 $ that $ {F}{\\left( k \\right)} = \\frac { 1 }{ \\sqrt { 5 }  } \\left[ { \\left( \\frac { 1+\\sqrt { 5 }  }{ 2 }  \\right)  }^{ k+1 }-{ \\left( \\frac { 1-\\sqrt { 5 }  }{ 2 }  \\right)  }^{ k+1 } \\right]  $ for each integer $ k $ such that $ 0 \\le k \\le n $."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Because we assumed that the above step holds up to $ n $, we have to look what happens at $ n + 1 $.  From recursion we know that $ {F}{\\left( n + 1 \\right)} = {F}{\\left( n \\right)} + {F}{\\left( n - 1 \\right)} $.  Both the right-hand side expressions have recursive steps $ \\le n $, so we can write the following\n",
    "$$ {F}{\\left( n + 1 \\right)} = \\left\\{ \\frac { 1 }{ \\sqrt { 5 }  } \\left[ { \\left( \\frac { 1+\\sqrt { 5 }  }{ 2 }  \\right)  }^{ n+1 }-{ \\left( \\frac { 1-\\sqrt { 5 }  }{ 2 }  \\right)  }^{ n+1 } \\right]  \\right\\} +\\left\\{ \\frac { 1 }{ \\sqrt { 5 }  } \\left[ { \\left( \\frac { 1+\\sqrt { 5 }  }{ 2 }  \\right)  }^{ n+1-1 }-{ \\left( \\frac { 1-\\sqrt { 5 }  }{ 2 }  \\right)  }^{ n+1-1 } \\right]  \\right\\} \\\\ {F}{\\left( n + 1 \\right)} = \\left\\{ \\frac { 1 }{ \\sqrt { 5 }  } \\left[ { \\left( \\frac { 1+\\sqrt { 5 }  }{ 2 }  \\right)  }^{ n+1 }-{ \\left( \\frac { 1-\\sqrt { 5 }  }{ 2 }  \\right)  }^{ n+1 } \\right]  \\right\\} +\\left\\{ \\frac { 1 }{ \\sqrt { 5 }  } \\left[ { \\left( \\frac { 1+\\sqrt { 5 }  }{ 2 }  \\right)  }^{ n }-{ \\left( \\frac { 1-\\sqrt { 5 }  }{ 2 }  \\right)  }^{ n } \\right]  \\right\\} $$\n",
    "If we replace $ a = \\frac{1 + \\sqrt{5}}{2} $ and $ b = \\frac{1 - \\sqrt{5}}{2} $ we have\n",
    "$$ F\\left( n+1 \\right) =\\frac { 1 }{ \\sqrt { 5 }  } \\left( { a }^{ n+1 }-{ b }^{ n+1 }+{ a }^{ n }-{ b }^{ n } \\right) \\\\ F\\left( n+1 \\right) =\\frac { 1 }{ \\sqrt { 5 }  } \\left[ { a }^{ n }\\left( a+1 \\right) -{ b }^{ n }\\left( b+1 \\right)  \\right] =\\frac { 1 }{ \\sqrt { 5 }  } \\left( { a }^{ n+2 }-{ b }^{ n+2 } \\right)  $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, have a look at this.  We will use *sympy* to show that $ \\left( a + 1 \\right) = {a}^{2} $ and $ \\left( b + 1 \\right) = {b}^{2} $."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\frac{1}{2} + \\frac{\\sqrt{5}}{2}$$"
      ],
      "text/plain": [
       "      ___\n",
       "1   ╲╱ 5 \n",
       "─ + ─────\n",
       "2     2  "
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = (1 + sym.sqrt(5)) / 2\n",
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\frac{\\sqrt{5}}{2} + \\frac{3}{2}$$"
      ],
      "text/plain": [
       "  ___    \n",
       "╲╱ 5    3\n",
       "───── + ─\n",
       "  2     2"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\frac{\\sqrt{5}}{2} + \\frac{3}{2}$$"
      ],
      "text/plain": [
       "  ___    \n",
       "╲╱ 5    3\n",
       "───── + ─\n",
       "  2     2"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(a**2).simplify()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(a + 1) == (a**2).simplify()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$- \\frac{\\sqrt{5}}{2} + \\frac{1}{2}$$"
      ],
      "text/plain": [
       "    ___    \n",
       "  ╲╱ 5    1\n",
       "- ───── + ─\n",
       "    2     2"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b = (1 - sym.sqrt(5)) / 2\n",
    "b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(b + 1) == (b**2).simplify()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, then, the equation for $ {F}{\\left( n \\right)} $ works for $ {F}{\\left( n + 1 \\right)} $ and our proof is complete."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Back to the top](#In-this-lesson)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}