{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter16 - Recurrance relations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ex16.14 Pg 536"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "for recurrence relation a(n)=5*a(n-1)-4*a(n-2)+n**2\n",
      "Value of a(2) is: 10 \n",
      "\n",
      "Value of a(3) is: 51 \n",
      "\n",
      "for recurrence relation a(n)=2*a(n-1)*a(n-2)+n**2\n",
      "Value of a(2) is: 8 \n",
      "\n",
      "Value of a(3) is: 41 \n",
      "\n",
      "for recurrence relation a(n)=n*a(n-1)+3*a(n-2)\n",
      "Value of a(2) is: 7 \n",
      "\n",
      "Value of a(3) is: 27 \n",
      "\n",
      "for recurrence relation a(n)=2*a(n-1)+5*a(n-2)-6*a(n-3)\n",
      "Value of a(2) is: 1 \n",
      "\n",
      "Value of a(3) is: 3 \n",
      "\n"
     ]
    }
   ],
   "source": [
    "a=[]#\n",
    "a.append(1)#  #initial condition\n",
    "a.append(2)#  #initial condition\n",
    "print 'for recurrence relation a(n)=5*a(n-1)-4*a(n-2)+n**2' #this is a second order recurrence relation with constant coefficients.It is non homogenous because of the n**2\n",
    "for n in range(2,4):\n",
    "    a.append(5*a[n-1]-4*a[n-2]+n**2)\n",
    "    print 'Value of a(%d) is: %d \\n'%(n,a[n])\n",
    "\n",
    " \n",
    "a=[]#\n",
    "a.append(1)#  #initial condition\n",
    "a.append(2)#  #initial condition\n",
    "print 'for recurrence relation a(n)=2*a(n-1)*a(n-2)+n**2'  #this recurrence relation is not linear\n",
    "for n in range(2,4):\n",
    "    a.append(2*a[(n-1)]*a[(n-2)]+n**2)\n",
    "    print 'Value of a(%d) is: %d \\n'%(n,a[n])\n",
    "\n",
    " \n",
    "a=[]#\n",
    "a.append(1)#  #initial condition\n",
    "a.append(2)#  #initial condition\n",
    "print 'for recurrence relation a(n)=n*a(n-1)+3*a(n-2)'   #this is a homogenous linear second order recurrence relation without constant coefficients because the coefficient of a[n-1] is n,not a constant\n",
    "for n in range(2,4):\n",
    "    a.append(n*a[(n-1)]+3*a[(n-2)])\n",
    "    print 'Value of a(%d) is: %d \\n'%(n,a[n])\n",
    "\n",
    "\n",
    " \n",
    "a=[]#\n",
    "a.append(1)#  #initial condition\n",
    "a.append(2)#  #initial condition\n",
    "a.append(1)#  #initial condition\n",
    "print 'for recurrence relation a(n)=2*a(n-1)+5*a(n-2)-6*a(n-3)' #this is a homogenous linear third order recurrence relation with constant coefficients.Thus we need three,not two,initial conditions to yield a unique solution of the recurrence relation\n",
    "for n in range(2,4):\n",
    "    a.append(2*a[(n-1)]+5*a[(n-2)]-6*a[(n-3)])\n",
    "    print 'Value of a(%d) is: %d \\n'%(n,a[n])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ex16.15 Pg 539"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "recurrence relation of Fibonacci numbers f[n]=f[n-1]+f[n-2]\n",
      "characterstic equation of the recurrence relation is: x**2 - x - 1\n",
      "roots of the characterstic equation j1,j2 are :\n",
      "1/2 + sqrt(5)/2 \t-sqrt(5)/2 + 1/2 \t\n",
      "\n",
      "for general equation fn=Ar**n+Br**n,values of Aand B respectively are calculated as:\n",
      "initial condition at n=0 and n=1 respectively are:\n",
      "[[ 1.618034 -0.618034]] [[ 2.61803403  0.38196603]]\n",
      "thus the solution is f[n]=0.4472136*((1.618034)**n-(- 0.4472136)**n)]\n"
     ]
    }
   ],
   "source": [
    "from numpy import mat\n",
    "from sympy import symbols, solve\n",
    "print 'recurrence relation of Fibonacci numbers f[n]=f[n-1]+f[n-2]'  \n",
    "x=symbols('x')\n",
    "g=x**2-x-1\n",
    "print 'characterstic equation of the recurrence relation is:',g\n",
    "j=solve(g,x)#\n",
    "print 'roots of the characterstic equation j1,j2 are :'\n",
    "for x in j:\n",
    "    print x,'\\t',\n",
    "\n",
    "print '\\n'\n",
    "print 'for general equation fn=Ar**n+Br**n,values of Aand B respectively are calculated as:'\n",
    "print 'initial condition at n=0 and n=1 respectively are:'\n",
    "f1=1#  \n",
    "f2=1#  \n",
    "#putting the values of f1 and f2 we get the equations to solve \n",
    "\n",
    "D=mat([[1.6180340, -0.618034],[(1.6180340)**2,  (-0.618034)**2]])#\n",
    "K=mat([[1, 1]])\n",
    "c=[]#\n",
    "c=D/K#\n",
    "A=c[0]\n",
    "B=c[1]\n",
    "print A, B\n",
    "print 'thus the solution is f[n]=0.4472136*((1.618034)**n-(- 0.4472136)**n)]'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ex16.17 Pg 543"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The recurrence relation t[n]=4(t[n-1]-t[n-2])\n",
      "characterstic polynomial equation for the above recurrence relation :  x**2 - 4*x + 4\n",
      "roots of the characterstic equation j1,j2 : \n",
      "2 \t\n",
      "\n",
      "the general solution is t[n]=n*2**n\n",
      "initial condition at n=0 and n=1 respectively are:\n",
      "[[ 1.   1. ]\n",
      " [-0.5 -0.5]] \t[[ 1.   1. ]\n",
      " [-0.5 -0.5]] \t\n",
      "thus the solution is t{n}=2*n-n*2**(n-1)\n"
     ]
    }
   ],
   "source": [
    "from numpy import mat\n",
    "from sympy import symbols, solve\n",
    "print 'The recurrence relation t[n]=4(t[n-1]-t[n-2])'\n",
    "x=symbols('x')\n",
    "g=x**2-4*x+4\n",
    "print 'characterstic polynomial equation for the above recurrence relation : ',g \n",
    "j=solve(g, x)\n",
    "print 'roots of the characterstic equation j1,j2 : '\n",
    "for x in j:\n",
    "    print x,'\\t'\n",
    "print ''\n",
    "print 'the general solution is t[n]=n*2**n' \n",
    "print 'initial condition at n=0 and n=1 respectively are:'\n",
    "t0=1#\n",
    "t1=1#\n",
    "#putting the values of t0 and t1 we get the equations to solve\n",
    "D=mat([[1, 0],[2, 2]])\n",
    "K=mat([[1, 1]])\n",
    "from numpy.linalg import solve\n",
    "c=solve(D,K)\n",
    "for cc in c:\n",
    "    print c,'\\t',\n",
    "print ''\n",
    "D=mat([[1, 0],[2, 2]])\n",
    "K=mat([[1, 1]])\n",
    "c=D/K#\n",
    "c1=c[0]\n",
    "c2=c[1]\n",
    "print 'thus the solution is t{n}=2*n-n*2**(n-1)'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ex16.18 Pg 544"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The recurrence relation a[n]=2*a[n-1]-3a[n-2]\n",
      "characterstic polynomial equation for the above recurrence relation :  x**2 - 2*x - 3\n",
      "roots of the characterstic equation j1,j2 : \n",
      "-1 \t3 \t\n",
      "the general solution is a[n]=c1*3**n+c2*(-1)**n\n",
      "initial condition at n=0 and n=1 respectively are:\n",
      "[[1 0]] [[ 3 -1]]\n",
      "thus the solution is a[n]=0.75*(3**n)+0.25*(1**n)\n"
     ]
    }
   ],
   "source": [
    "from numpy import mat\n",
    "from sympy import symbols, solve\n",
    "print 'The recurrence relation a[n]=2*a[n-1]-3a[n-2]'\n",
    "x=symbols('x')\n",
    "g=x**2-2*x-3\n",
    "print 'characterstic polynomial equation for the above recurrence relation : ',g \n",
    "from sympy import solve\n",
    "j=solve(g, x)#\n",
    "print 'roots of the characterstic equation j1,j2 : '\n",
    "for x in j:\n",
    "    print x,'\\t',\n",
    "print \"\"\n",
    "print 'the general solution is a[n]=c1*3**n+c2*(-1)**n' \n",
    "print 'initial condition at n=0 and n=1 respectively are:'\n",
    "#putting the values of t0 and t1 we get the equations to solve\n",
    "a0=1#\n",
    "a1=2#\n",
    "D=mat([[1, 1],[3, -1]])\n",
    "K=mat([[1, 2]])\n",
    "c=D/K#\n",
    "c1=c[0]\n",
    "c2=c[1]\n",
    "print c1, c2\n",
    "print 'thus the solution is a[n]=0.75*(3**n)+0.25*(1**n)'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ex16.19 Pg 556"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The recurrence relation a[n]=11*a[n-1]-39*a[n-2]+45*a[n-3]\n",
      "characterstic polynomial equation for the above recurrence relation :  x**3 - 11*x**2 + 39*x - 45\n",
      "roots of the characterstic equation j1,j2 : \n",
      "3 \t5 \t\n",
      "hence the general solution is:a[n]=c1*(3**n)+c2*n*(3**n)+c3*(5**n)\n",
      "initial condition at n=0 and n=1 respectively are:\n",
      "[[0 0 0]] [[0 0 0]] [[1 1 1]]\n",
      "thus the solution is a[n]=(4-2*n)*(3**n)+5**n\n"
     ]
    }
   ],
   "source": [
    "from numpy import mat\n",
    "from sympy import symbols, solve\n",
    "print 'The recurrence relation a[n]=11*a[n-1]-39*a[n-2]+45*a[n-3]'\n",
    "x=symbols('x')\n",
    "g=x**3-11*x**2+39*x-45\n",
    "print 'characterstic polynomial equation for the above recurrence relation : ',g \n",
    "j=solve(g, x)\n",
    "print 'roots of the characterstic equation j1,j2 : '\n",
    "for x in j:\n",
    "    print x,'\\t',\n",
    "print ''\n",
    "print 'hence the general solution is:a[n]=c1*(3**n)+c2*n*(3**n)+c3*(5**n)'\n",
    "print 'initial condition at n=0 and n=1 respectively are:'\n",
    "#putting the values of t0 and t1 we get the equations to solve\n",
    "a0=5#\n",
    "a1=11#\n",
    "a2=25#\n",
    "D=mat([[1, 0 ,1],[3, 3, 5],[9, 18, 25]])\n",
    "K=mat([[5, 11, 25]])\n",
    "c=D/K#\n",
    "c1=c[0]\n",
    "c2=c[1]\n",
    "c3=c[2]\n",
    "print c1, c2, c3\n",
    "print 'thus the solution is a[n]=(4-2*n)*(3**n)+5**n'"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}