{
 "metadata": {
  "name": "",
  "signature": "sha256:501c2a82f9b3836f9ff0dcfbb99a68b21da826cceee29ea5d48167dee7fbaa2f"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from sympy import init_printing\n",
      "init_printing()\n",
      "import sympy as sym"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 7
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# \u5b9a\u7fa9\n",
      "\n",
      "- f(1) = 1\n",
      "- f(2) = 1\n",
      "- f(n) = f(n-1) + f(n-2)"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import numpy as np\n",
      "def fib(n):\n",
      "    A = np.array([[0,1],[1,1]])\n",
      "    tmp = np.array([0,1])\n",
      "    for i in xrange(1,n):\n",
      "        tmp = tmp.dot(A)\n",
      "    return tmp[1]\n",
      "\n",
      "print(map(fib, range(15)))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]\n"
       ]
      }
     ],
     "prompt_number": 8
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "F, Fx1, Fx2, F0, F1 = sym.symbols(\"F(x) F(x-1) F(x-2) F(0) F(1)\")\n",
      "print(sym.Eq(F0, 0))\n",
      "print(sym.Eq(F1, 1))\n",
      "print(sym.Eq(F, sym.Add(Fx1, Fx2)))\n",
      "\n",
      "x = sym.Symbol('x')\n",
      "sym.solve([sym.Eq(F0, 0), sym.Eq(F1, 1), sym.Eq(F, sym.Add(Fx1, Fx2))], [x])\n",
      "print(sym.solve([x], [x]))\n",
      "print(sym.solve([x-1], [x]))\n",
      "print(F.series(x, 0, 5))\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "F(0) == 0\n",
        "F(1) == 1\n",
        "F(x) == F(x-1) + F(x-2)\n",
        "{x: 0}"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "{x: 1}\n",
        "F(x)\n"
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from sympy.abc import n\n",
      "fib = sym.Function('fib')\n",
      "f = fib(n) - fib(n-1) - fib(n-2)\n",
      "sym.rsolve(f, fib(n), {fib(0):0, fib(1):1})"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "latex": [
        "$$\\frac{\\sqrt{5}}{5} \\left(\\frac{1}{2} + \\frac{\\sqrt{5}}{2}\\right)^{n} - \\frac{\\sqrt{5}}{5} \\left(- \\frac{\\sqrt{5}}{2} + \\frac{1}{2}\\right)^{n}$$"
       ],
       "metadata": {},
       "output_type": "pyout",
       "png": "iVBORw0KGgoAAAANSUhEUgAAAWwAAAAkCAYAAACt4wAMAAAABHNCSVQICAgIfAhkiAAACFVJREFU\neJztnXuoFUUcxz9XDS18ZVmWVlaXSArl9qYnRYSBBGXaQzEs6U3Zg/rDilKhKHpS2NvNXoZSUVhm\nEWZPikoSsqgsy8IkLbq9qW5//Pbgtmcfs7Mz+zrzgQP37tkz85vffH+zszOzs+BwOByOWtC/bAMU\n6Od/+so2pCHUoc6bjtN0tahNTPQr24AUBgAesE/JdjSJfYGHEd86isdpunp0XEwcBIywkO6jwIkW\n0i0SW77JwyREoI54OkHTVdRmWXRUTPQZ+IS5ALjbtuEF8AJ2/JOXe4GZFtJtCp2g6apqsyw6IiYm\nAlcbTnMM8CUwxHC6RWPDN6YYBqwDRpVtSAXpBE1XWZtl0REx8Rww1HCaC2mGmGz4xiRzkF6F4/90\ngqarrs2yaHRMHAHMN5zmGKCXeDENAZYCuxvO1zQ2fGOa4YivG92jyEgZmi6aOmjTJFnajEbHxBJg\npOE0r/fTjWKW/30fMNZwvqax4ZsoTsn5+6eRXoVt8tpZFEVrugzqok0T6LQZjYyJCcCdFtJdC5yZ\nck7VG2xbvgmzL/BszjSmA2sM2JKECTuLoExNF0WdtGmSLG1GI2NiEeaHJcYijh2dcl7VG2wbvoli\nLnBa6NghSA/hRUR0D5Hsz90Qf44JHR8BXIaI6jBk9nw2cKshOz9FAmM0cht6PPAKME4jfVOUqemi\nqJM2TZKlzWhcTHQDD6aco5P5DOBrhfyr3GCr+AbMVM4HwLaB/w8AVvjpAQwGVgGbSPbXt7T3AGcB\n2wCfAaf7x4YCv2awL85OaF8a9hdwkUbapihb00Vgq4xRmNKmKbK2GY2KifuQLn0SOpnfCSxXyN9E\ngz0eO082qfgG8lfOIchDGEGWIUEZpMdPf3FCWq8AN4eODUGCNtjYHAu8l8HGODsB1gP3A8/4eZfZ\ns4byNV0EtsoYxqQ2o9CJ3axtRiVjIq7QQ5CZ0ihG+99/kmLU18BLyOTGZ8iyprUpvxmHXOGL4HJk\nMuKrjL8z4RvQ80+QacAToWPHAK8iT7Bt8o99CPyE9JTi+IL2QO4FTvbTazEFeApZr/ozag9NRNkJ\nsib5XIXfm6ITNF1WGcOY1GYUurGbhVrExHbA48A9CefcChyokNbKLBn7rEVtdtZED9vLmIZJ34Ce\nf1r0Bz6i/YK7BvgT2DN0fCPJt21zkVu0MI8gt/QAXcAPyLjeFTnthHzlz0JdNJ2HsssYxLQ2o/DI\nHv9Z24xKxkRw86cByJVrnW9Q1JrREYjD31c0Lis7IQ6IYxqwwP/7JuBiS3aEqYJvghwHvA78HTp+\nGLAHcqVusSuwM/BuQnqb/XPCdAMv+3/3Ae8AJwBv5LQTYCBwLXAHcAsyGWV6Q6Qq1FuapvNShTIG\nMa3NvOi2GbWJiRHAb8ClEd/dgIzZqPC2Rua/A2cppp8Xj+xXaVO+AT3/tFiIPPygwk3AP8DhCeec\nB2xRTC8LSXZ+jszGt5gOfI+dBxY6QdNlljGIaW1G4WF/orJWMfEAMu7WFTg2GJk4UEUn83+BMzLk\nkQcPvUo34RvQr5xBwOpQ/nF0A7+Q/lTb2ejNdCeRZmd4a9/+SINzl2E7WnSCpssqYwsb2ozCw36D\nXauYmIB09ycGjl0JnJTBOJ3Mq97DBjO+Af3KmQzcqJD+QORW8zaFc8/HfG9C1c4g6/1PiwnIxNRq\nxc/ChLSrqukmlLGFDW1G4WG/wa5qTMSyiq1X5oHIzLHKlTNP5puRWxGTPEK08LcAH8d8lzY5Y8M3\noFY5S4H9U87pQmah5yrmOxvYoHiuKkl2rkLG8cJsAP4wbEc43yZoOokyytjCtDZtxK4qtYuJKcjt\nXDciuGkZDNPN/GPiZ9RN78vroX+VzuMb0PfPMNQmaOYj45BBZkSdGDjf5IRUmp29SK8yzB/YXQJX\nNU3boIwygj1tRuGhFrt52oxKxkTSK8KeAb4DLgFOJdvi9h5k7CzMjiRfqb8hfqysS+FTFHl8A/r+\nmYxMAiUxEwnYeaHjRyb8ZmfE96ZIs3M57Wtve5Ae4WMG7QhTNU3boIwygj1t5iFPm1HLmJiDOPj8\njMYtAXaIyLyP9qtrkNsp7qkwj3zjYLq+AX3/rECWRsVxHLKE7LHQZzHwZMLvVpJ9bC2JNDsPRm4P\nt/P/70L2uHgLEahNmqzpFkWXEexpMwoP+2PYK6lhTIxEZo0HZTRON/PpFLfvgke+Stf1Dej5ZxTw\nWkq6PxJ/6xfu1QTZSPtGNLqo2AlwFNJALEI205mHni+z0mRNtyi6jDa1GYWH/Qa7k2JCO/PWLllx\nO3gdiuyWdT2yeP3oHPZ5lLuBVFb/zAYutGDHXojPdzGUni07q4ANTVcNnTIWXece6rGr02a4mMjA\nGqInSgYjC+1bTEWWG+kGwl3U660SbyJjiaY5m+jJDl1s2Vln4jTdFIquc9XY1W0zXExkYA7Rg/Pj\nkXG5vf3/hyJXwakF2VUm3WR/MEeVZcBVhtKyaWedidN0E6hyneu2GS4mMjAKWeKyfeh4F3J705rZ\n3Q9xfk9xppXGdchYqGlGIr429booW3bWnThNN4Eq17lOm+FiQoMFwDUp5zyK3pse6sjzRC+3yst8\nzL4uypadTUBF03WkTnWu0ma4mNBgFLKr1/CY789BNvgucu1109gB8XFjx9YqRpqmHXZRaTNcTORg\nBrKZTZhJiPNBZq/HFmVQw1jE1tccOYohTtMOu6i2GZWPiaQnHctmEbL14smBY8cgTyAtQ3osEzG3\n9KaTmIqM02V9QtORjyhNO+yi2ma4mDBAP6RHsj+yNrKX9kX3URu2O+IZj7zbr8oX6yYT1LTDLqpt\nhosJh8PhcDgcDofD4XA4HI7q8h8SF2F5WsfvngAAAABJRU5ErkJggg==\n",
       "prompt_number": 4,
       "text": [
        "                 n                      n\n",
        "      \u239b      ___\u239e          \u239b    ___    \u239e \n",
        "  ___ \u239c1   \u2572\u2571 5 \u239f      ___ \u239c  \u2572\u2571 5    1\u239f \n",
        "\u2572\u2571 5 \u22c5\u239c\u2500 + \u2500\u2500\u2500\u2500\u2500\u239f    \u2572\u2571 5 \u22c5\u239c- \u2500\u2500\u2500\u2500\u2500 + \u2500\u239f \n",
        "      \u239d2     2  \u23a0          \u239d    2     2\u23a0 \n",
        "\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500 - \u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\n",
        "        5                     5          "
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from sympy.abc import n\n",
      "fib = sym.Function('fib')\n",
      "f = fib(n) - fib(n-1) - fib(n-2)\n",
      "term = sym.rsolve(f, fib(n), {fib(0):0, fib(1):1})\n",
      "print(term)\n",
      "for i in xrange(1,10):\n",
      "    print(term.evalf(subs={n:i}))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "sqrt(5)*(1/2 + sqrt(5)/2)**n/5 - sqrt(5)*(-sqrt(5)/2 + 1/2)**n/5\n",
        "1.00000000000000\n",
        "1.00000000000000\n",
        "2.00000000000000\n",
        "3.00000000000000\n",
        "5.00000000000000\n",
        "8.00000000000000\n",
        "13.0000000000000\n",
        "21.0000000000000\n",
        "34.0000000000000\n"
       ]
      }
     ],
     "prompt_number": 5
    }
   ],
   "metadata": {}
  }
 ]
}