{ "nbformat": 4, "nbformat_minor": 0, "metadata": { "colab": { "provenance": [], "authorship_tag": "ABX9TyOtICZufJdg+ET9DecNXukr", "include_colab_link": true }, "kernelspec": { "name": "python3", "display_name": "Python 3" }, "language_info": { "name": "python" } }, "cells": [ { "cell_type": "markdown", "metadata": { "id": "view-in-github", "colab_type": "text" }, "source": [ "\"Open" ] }, { "cell_type": "markdown", "source": [ "# Recursion" ], "metadata": { "id": "f4urMg7qAhI2" } }, { "cell_type": "markdown", "source": [ "Recursion is one of these topics then when you see it once, you'll see it again and again forever. Terrible I know...\n", "\n", "Seriously it is best described as a function that calls itself. We see these often in simple mathematical questions. \n", "\n", "\n", "\n" ], "metadata": { "id": "Lv7NbtIOAo8-" } }, { "cell_type": "markdown", "source": [ "## Exponential Growth\n", "\n", "Consider a population of aemebas that double every cycle. Write a recursive relationship describing this doubling. \n", "\n", "We see simply that $f(n+1) = 2f(n)$ so if you go to the new cycle, $n+1$, you will be double the previous. The question then arrifes how do we write the function $f(n)$ where it does not reference itself?\n", "\n", "If you recall college algebra, you can write this function as $f(n) = P_02^n$ Here $P_0$ is some initial population. \n", "\n", "Let's code both of these by setting $f(0) = P_0 = 1$ (we always need an initial conditon to fully sovle these equations)" ], "metadata": { "id": "hAezWHlrBKD1" } }, { "cell_type": "code", "execution_count": null, "metadata": { "id": "m3GEAsHAAf58" }, "outputs": [], "source": [ "def f_recursive(n):\n", " if n>=1:\n", " return 2*f_recursive(n-1)\n", " elif n==0:\n", " return 1\n", "\n", "def f_exponential(n):\n", " return 1*2**n" ] }, { "cell_type": "markdown", "source": [], "metadata": { "id": "j0yXIzlxC2vS" } }, { "cell_type": "code", "source": [ "f_recursive(5)" ], "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "c8xbQ3HXCusm", "outputId": "de73e9bc-d1cc-4b7b-b957-e05a73711aec" }, "execution_count": null, "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "32" ] }, "metadata": {}, "execution_count": 5 } ] }, { "cell_type": "code", "source": [ "f_exponential(5)" ], "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "kmqFTf5DDHEb", "outputId": "ab85f06b-f52e-4119-cbd7-36753e036ac0" }, "execution_count": null, "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "32" ] }, "metadata": {}, "execution_count": 8 } ] }, { "cell_type": "markdown", "source": [ "We'll look at the graphs of each." ], "metadata": { "id": "YKLEcDk2DPzy" } }, { "cell_type": "code", "source": [ "import matplotlib.pyplot as plt\n", "import numpy as np\n", "\n", "x = np.linspace(0,5,100)\n", "y = f_exponential(x)\n", "\n", "z = range(0,6)\n", "zz = [f_recursive(i) for i in z]\n", "\n", "plt.scatter(z,zz)\n", "plt.plot(x,y)" ], "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 448 }, "id": "AY60BjcbDMti", "outputId": "add85974-2c20-44b9-bbe8-ba08779fd89d" }, "execution_count": null, "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "[]" ] }, "metadata": {}, "execution_count": 12 }, { "output_type": "display_data", "data": { "text/plain": [ "
" ], "image/png": "iVBORw0KGgoAAAANSUhEUgAAAh8AAAGdCAYAAACyzRGfAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjcuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/bCgiHAAAACXBIWXMAAA9hAAAPYQGoP6dpAAA7F0lEQVR4nO3deXxU9aH+8WeyTUKWCdkTkkDYwiYgCBgXKogstRQqVqUuaPnZ6kVb5Hrb0tuK3Npi21urvSra3hariLiColcoooALO0Y22QMkZCdkJglkksyc3x/BSCAgSSZzZiaf9+t1XiRnTmYepzTz8D3f8z0WwzAMAQAAeEmQ2QEAAEDnQvkAAABeRfkAAABeRfkAAABeRfkAAABeRfkAAABeRfkAAABeRfkAAABeFWJ2gHO53W4VFhYqOjpaFovF7DgAAOASGIahqqoqpaWlKSjo4mMbPlc+CgsLlZGRYXYMAADQBvn5+UpPT7/oMT5XPqKjoyU1ho+JiTE5DQAAuBQOh0MZGRlNn+MX43Pl46tTLTExMZQPAAD8zKVMmWDCKQAA8CrKBwAA8CrKBwAA8CrKBwAA8CrKBwAA8CrKBwAA8CrKBwAA8CrKBwAA8CqfW2QMAAB0DJfb0Oa8CpVW1SopOlwjs+IUHOT9+6hRPgAA6ARW7irS/BV7VGSvbdqXagvXvMkDNHFQqlezcNoFAIAAt3JXke5fvL1Z8ZCkYnut7l+8XSt3FXk1D+UDAIAA5nIbmr9ij4wWHvtq3/wVe+Ryt3REx6B8AAAQwDbnVZw34nE2Q1KRvVab8yq8lonyAQBAACutunDxaMtxnkD5AAAggCVFh3v0OE+gfAAAEMBGZsUp1XbhYmFR41UvI7PivJaJ8gEAQAALDrJo3uQBLT721Qof8yYP8Op6H5QPAAAC3ISBKUqKtp63P8UWroV3DPP6Oh8sMgYAQIDbevSkSquc6hIWrGd+MEyO2npWOAUAAB3n9a35kqQbL0vVmH5JJqfhtAsAAAGtxtmgd3c0rmB6y4gMk9M0onwAABDA3ttZpFN1LmUlROqK7l3NjiOJ8gEAQEB7Y2uBJOnm4emyWLw/v6MllA8AAALU4bJqbT5SoSCLNG1YutlxmlA+AAAIUG9saxz1+FbfRKVcZKExb6N8AAAQgBpc7qby8f0rfGOi6VcoHwAABKAP95aqtMqp+MgwjeufbHacZigfAAAEoKVbGtf2uHl4usJCfOvj3rfSAACAdiuyn9bafaWSpFt9ZG2Ps1E+AAAIMK9tKZDbkEZlxalnYpTZcc5D+QAAIIC43IZeO7Oc+vSRmSanaVmrysfChQs1ePBgxcTEKCYmRjk5OXr//febHq+trdWsWbMUHx+vqKgoTZs2TSUlJR4PDQAAWrb+QJmOV56WLSJUEwelmB2nRa0qH+np6Xr88ce1bds2bd26VWPHjtWUKVO0e/duSdJDDz2kFStW6PXXX9e6detUWFiom266qUOCAwCA8y3dfEyS9L3Luyk8NNjkNC2zGIZhtOcJ4uLi9Mc//lE333yzEhMTtWTJEt18882SpL1796p///7asGGDrrzyykt6PofDIZvNJrvdrpiYmPZEAwCgUymtqtVVCz5Ug9vQqtmjlZ0S7bXXbs3nd5vnfLhcLi1dulQ1NTXKycnRtm3bVF9fr3HjxjUd069fP2VmZmrDhg0XfB6n0ymHw9FsAwAArffGtgI1uA0Ny4z1avForVaXj507dyoqKkpWq1X33Xefli1bpgEDBqi4uFhhYWGKjY1tdnxycrKKi4sv+HwLFiyQzWZr2jIyfO+SIAAAfJ3bbejVM2t73OajE02/0urykZ2drdzcXG3atEn333+/ZsyYoT179rQ5wNy5c2W325u2/Pz8Nj8XAACd1YbDJ3T0xClFW0P0ncGpZse5qJDW/kBYWJh69+4tSRo+fLi2bNmip556Srfeeqvq6upUWVnZbPSjpKREKSkXnm1rtVpltVpbnxwAADR5edNRSdKUy9PUJazVH+9e1e51Ptxut5xOp4YPH67Q0FCtWbOm6bF9+/bp2LFjysnJae/LAACACyh11OpfuxuXtrjjyu4mp/lmrapGc+fO1aRJk5SZmamqqiotWbJEa9eu1apVq2Sz2TRz5kzNmTNHcXFxiomJ0YMPPqicnJxLvtIFAAC03tIt+WpwG7qie1f1S/H9K0VbVT5KS0t11113qaioSDabTYMHD9aqVat0ww03SJL+/Oc/KygoSNOmTZPT6dSECRP07LPPdkhwAAAgNbjceuXM2h7+MOoheWCdD09jnQ8AAC7dv3YX60cvbVPXLqHaMPd60xYW88o6HwAAwHwvb2oc9bjligyfXdH0XJQPAAD81LETp7T+QJkk6QejfHttj7NRPgAA8FMvbz4qw5BG901U9/hIs+NcMsoHAAB+yNng0utbCyRJd/jRqIdE+QAAwC+9v7NYFTV1SrWFa2y/JLPjtArlAwAAP7R4Y+OKptNHZiok2L8+zv0rLQAA0O5Cu7YePamQIItuG+F/N2SlfAAA4Gde/Kxx1GPioBQlxYSbnKb1KB8AAPiRkzV1Wp57XJJ091U9zA3TRpQPAAD8yGtb8+VscGtAaoyGd+9qdpw2oXwAAOAnXG5DL52ZaHr3VT1ksVhMTtQ2lA8AAPzEh3tLVXDytGK7hOq7Q9PMjtNmlA8AAPzEPz87Ikm6dYT/3MelJZQPAAD8wMHSKn1ysFxBFumOUd3NjtMulA8AAPzAixsa53pc3z9ZGXFdTE7TPpQPAAB8XFVtvd7c1ngfF3+9vPZslA8AAHzcG9sKVFPnUu+kKF3VK97sOO1G+QAAwIe53IZeODPRdEZOd7+9vPZslA8AAHzYh3tLdfTEKdkiQjVteLrZcTyC8gEAgA/7xyd5khrvXtslLMTkNJ5B+QAAwEftLrRrw+ETCg6y6K4c/7689myUDwAAfNSiT49IkiYNSlFabIS5YTyI8gEAgA8qrarVO7mFkqSZ12SZnMazKB8AAPiglzceU53LrcszY3V5pn/evfZCKB8AAPiY2nqXXt7UuKLpD68OrFEPifIBAIDPeeeLQpVX1ynNFq5Jg1LMjuNxlA8AAHyIYRhNl9fedVUPhQQH3kd14P0XAQDgxz45WK69xVWKCA3WbSMyzI7TISgfAAD4kL+uPyxJunVEhmK7hJmcpmNQPgAA8BFfFjn08YFyBVkC7/Las1E+AADwEX87M+ox6bJUZcR1MTlNx6F8AADgA4rsp/XOF42Liv14dE+T03QsygcAAD5g0adH1OA2NCorToPTY82O06EoHwAAmMxRW68lm45Jkn78rcAe9ZAoHwAAmG7p5mOqdjaod1KUruubZHacDkf5AADARHUNbv3jkyOSpB9d21NBQRZzA3kB5QMAABO9u6NQxY5aJUZbNeXyNLPjeAXlAwAAk7jdhp5bd0iSdPdVPWQNCTY5kXdQPgAAMMmHe0u1v6RaUdYQ3XFld7PjeA3lAwAAExiGoWfXHpQk3X5lpmwRoSYn8h7KBwAAJticV6HtxyoVFhKkmVcH7lLqLaF8AABggoVn5nrcPDxdSTHhJqfxLsoHAABetrvQrrX7yhRkCfyl1FvSqvKxYMECjRgxQtHR0UpKStLUqVO1b9++Zsdcd911slgszbb77rvPo6EBAPBnz61rvIHcjYPT1D0+0uQ03teq8rFu3TrNmjVLGzdu1OrVq1VfX6/x48erpqam2XH33nuvioqKmrY//OEPHg0NAIC/OlJeo/d2NN5A7v5v9TI5jTlCWnPwypUrm33/wgsvKCkpSdu2bdPo0aOb9nfp0kUpKSmeSQgAQAB5fv1huQ3puuxEDUiLMTuOKdo158Nut0uS4uLimu1/+eWXlZCQoEGDBmnu3Lk6derUBZ/D6XTK4XA02wAACEQljlq9ua1AkvRv1/U2OY15WjXycTa3263Zs2fr6quv1qBBg5r2/+AHP1D37t2VlpamHTt26Oc//7n27dunt956q8XnWbBggebPn9/WGAAA+I3n1x1WncutK7p31YgeXc2OYxqLYRhGW37w/vvv1/vvv69PPvlE6enpFzzuww8/1PXXX6+DBw+qV6/zz205nU45nc6m7x0OhzIyMmS32xUT0zmHowAAgae82qlrfv+hauvd+ucPR+pbfRPNjuRRDodDNpvtkj6/2zTy8cADD+jdd9/V+vXrL1o8JGnUqFGSdMHyYbVaZbVa2xIDAAC/8b8f56m23q0h6TaN7pNgdhxTtap8GIahBx98UMuWLdPatWuVlfXNK7Ll5uZKklJTU9sUEAAAf3eypk4vbTgiSXpwbB9ZLBZzA5msVeVj1qxZWrJkid5++21FR0eruLhYkmSz2RQREaFDhw5pyZIl+va3v634+Hjt2LFDDz30kEaPHq3Bgwd3yH8AAAC+btGneaqpc6l/aoyu759kdhzTtap8LFy4UFLjQmJnW7Roke6++26FhYXpgw8+0JNPPqmamhplZGRo2rRp+tWvfuWxwAAA+BNHbb0WfXZEkvTg2N6dftRDasNpl4vJyMjQunXr2hUIAIBA8s9Pj6iqtkF9kqI0cSBrYEnc2wUAgA5T7WzQ3z/NkyQ9MLa3goIY9ZAoHwAAdJjFG4+q8lS9shIi9Z3BaWbH8RmUDwAAOkCNs0F/Xd94A7l/u66Xghn1aEL5AACgA7y44agqaurUPb6Lvnd5N7Pj+BTKBwAAHlbtbNBf1x+SJP1kbB+FBPNxezbeDQAAPOyfnx3RyTNzPaYMZa7HuSgfAAB4UFVtfdNcj59c35tRjxbwjgAA4EEvfHpE9tP16pkYqe8OYa5HSygfAAB4iP10vf72ceOox0+v78MVLhdA+QAAwEMWfZonR22DeidFsa7HRVA+AADwAPupev39k8bVTBn1uDjKBwAAHvDXjw+pqrZBfZOjdONlqWbH8WmUDwAA2qmsyqlFnx6RJP37+Gzu4fINKB8AALTTs2sP6lSdS0PSbRo/INnsOD6P8gEAQDscrzytlzcekyT9x4R+slgY9fgmlA8AANrhLx8cUJ3LrZye8bq6d7zZcfwC5QMAgDY6VFatN7YXSJIenpDNqMclonwAANBGf169Xy63oXH9kzS8e1ez4/gNygcAAG2wu9Cud3cUSWq8wgWXjvIBAEAb/Olf+yVJ3x2Spv6pMSan8S+UDwAAWmnj4RP6cG+pgoMseuiGvmbH8TuUDwAAWsEwDC14f68kafrIDGUlRJqcyP9QPgAAaIX3dxXri/xKdQkL1k+vZ9SjLSgfAABconqXW39ctU+SdO+1PZUYbTU5kX+ifAAAcImWbslXXnmNEqLCdO/onmbH8VuUDwAALkGNs0FPfXBAkvST6/soyhpiciL/RfkAAOAS/O3jwyqvdqpHfBdNH5lpdhy/RvkAAOAblFU59bf1hyU1LqMeGszHZ3vw7gEA8A2e/GC/aupcGpJu042XpZodx+9RPgAAuIj9JVV6ZfMxSdJ/3jiAm8d5AOUDAICL+O17X8ptSBMHpmhkVpzZcQIC5QMAgAtYt79M6/aXKTTYol9M6md2nIBB+QAAoAUNLrd++94eSdJdOT3Ug2XUPYbyAQBAC17bWqD9JdWK7RKqn4ztY3acgEL5AADgHNXOBj2xunEZ9Z+M7SNbl1CTEwUWygcAAOdYuPagyqvrlJUQqTuu7G52nIBD+QAA4Cz5Faf0t4/zJEm/mNRPYSF8VHoa7ygAAGf53f99qboGt67qFa/xA5LNjhOQKB8AAJzx2aFyvb+rWEEW6ZHJLCjWUSgfAACo8dLa+e80Xlp7x5Xd1S8lxuREgYvyAQCApFc2H9O+kirFdgnVnBv6mh0noFE+AACdXuWpOv1p9X5J0r/f0FexXcJMThTYKB8AgE7vidX7VXmqXv1SojV9ZKbZcQJeq8rHggULNGLECEVHRyspKUlTp07Vvn37mh1TW1urWbNmKT4+XlFRUZo2bZpKSko8GhoAAE/ZW+zQ4o1HJTVOMg0J5t/lHa1V7/C6des0a9Ysbdy4UatXr1Z9fb3Gjx+vmpqapmMeeughrVixQq+//rrWrVunwsJC3XTTTR4PDgBAexmGoUfe3i23IU0alKKreiWYHalTsBiGYbT1h8vKypSUlKR169Zp9OjRstvtSkxM1JIlS3TzzTdLkvbu3av+/ftrw4YNuvLKK7/xOR0Oh2w2m+x2u2JimGkMAOg4yz8/rtmv5io8NEhr/v06dYuNMDuS32rN53e7xpbsdrskKS4uTpK0bds21dfXa9y4cU3H9OvXT5mZmdqwYUN7XgoAAI9y1Nbrt//3pSTpwbF9KB5eFNLWH3S73Zo9e7auvvpqDRo0SJJUXFyssLAwxcbGNjs2OTlZxcXFLT6P0+mU0+ls+t7hcLQ1EgAAl+zJ1QdUVuVUz4RI/b9rs8yO06m0eeRj1qxZ2rVrl5YuXdquAAsWLJDNZmvaMjIy2vV8AAB8ky+LHPrnhiOSpEe/O1DWkGBzA3UybSofDzzwgN5991199NFHSk9Pb9qfkpKiuro6VVZWNju+pKREKSkpLT7X3LlzZbfbm7b8/Py2RAIA4JI0TjLdJZfb0LcvS9HovolmR+p0WlU+DMPQAw88oGXLlunDDz9UVlbzYarhw4crNDRUa9asadq3b98+HTt2TDk5OS0+p9VqVUxMTLMNAICOsuzz49py5KQiQoP1qxsHmB2nU2rVnI9Zs2ZpyZIlevvttxUdHd00j8NmsykiIkI2m00zZ87UnDlzFBcXp5iYGD344IPKycm5pCtdAADoSPZT9frdmUmmP7m+j9KYZGqKVpWPhQsXSpKuu+66ZvsXLVqku+++W5L05z//WUFBQZo2bZqcTqcmTJigZ5991iNhAQBoj9+v2qvy6jr1SozUzGuYZGqWdq3z0RFY5wMA0BG2Ha3QtIWNyz68+qMrNapnvMmJAovX1vkAAMAf1Lvc+uVbuyRJ3x+eTvEwGeUDABDw/vfjPO0rqVJcZJh++e3+Zsfp9CgfAICAll9xSk+t2S9J+uW3+6trZJjJiUD5AAAELMMw9Kvlu1Rb79aVPeM0bVg3syNBlA8AQAB7b2eR1u0vU1hwkH77vctksVjMjgRRPgAAAepkTZ0efWe3JOm+63qpV2KUyYnwFcoHACAgPfbelyqvrlPvpCjNGtPL7Dg4C+UDABBw1u8v05vbC2SxSL+fNpgbx/kYygcAIKDUOBv0y2U7JUkzcnpoePeuJifCuSgfAICA8qd/7VfBydPqFhuh/5iQbXYctIDyAQAIGJ8fO6lFn+VJkn5302WKtLbqFmbwEsoHACAg1DW49Ys3d8owpJsu76Zv9U00OxIugPIBAAgI//PhAe0rqVJ8ZJh+/Z0BZsfBRVA+AAB+b2eBXc+uPSRJemzqIJZQ93GUDwCAX3M2uPTw61/I5Tb0ncGpmnRZqtmR8A0oHwAAv/Y/aw5qX0mVEqLC9F9TBpkdB5eA8gEA8Fs7Ciq1cN3Xp1viON3iFygfAAC/dPbplslD0jRxEKdb/AXlAwDgl5784ID2l1QrISpM87870Ow4aAXKBwDA72w9UqHnm063XMbpFj9D+QAA+JVqZ4PmvPaF3IZ007BumjgoxexIaCXKBwDAr/z2vT06VnFK3WIj9CinW/wS5QMA4DfWfFmiVzbny2KR/vv7QxQTHmp2JLQB5QMA4BdOVDv18zd3SJJmXp2lnF7xJidCW1E+AAA+zzAM/XLZTpVX16lvcpQenpBtdiS0A+UDAODzXt9aoFW7SxQabNETtwxVeGiw2ZHQDpQPAIBPO1xWrUdX7JYkzbkhW4O62UxOhPaifAAAfFZdg1s/XZqrU3Uu5fSM149H9zQ7EjyA8gEA8FlPrN6vncftiu0SqiduHaKgIIvZkeABlA8AgE/67GC5nl/fuIrp4zcNVqotwuRE8BTKBwDA55ysqdNDr+XKMKTpIzNZxTTAUD4AAD7FMAz9/M0dKnE41TMxUr/+Tn+zI8HDQswOAACAy21oc16FSqtqtf1opf61p0RhwUH6y22Xq0sYH1WBhv9FAQCmWrmrSPNX7FGRvbbZ/u9dnsZltQGK0y4AANOs3FWk+xdvP694SNKrWwu0cleRCanQ0SgfAABTuNyG5q/YI+MCj1skzV+xRy73hY6Av6J8AABMsTmvosURj68YkorstdqcV+G9UPAKygcAwBSlVRcuHm05Dv6D8gEAMEVSdLhHj4P/oHwAAEwxokdXhYdc+GPIIinVFq6RWXHeCwWvoHwAAEyx6NMjqm1wt/jYV3dwmTd5gIK5n0vAoXwAALxuc16FHl+5V5J024gMpdqan1pJsYVr4R3DNHFQqhnx0MFYZAwA4FWlVbV6YMl2udyGpgxN04KbLpPbUNMKp0nRjadaGPEIXJQPAIDXNLjc+skrn6u0yqk+SVH63fcuk8ViUbBFyukVb3Y8eEmrT7usX79ekydPVlpamiwWi5YvX97s8bvvvlsWi6XZNnHiRE/lBQD4sQXv79XGwxWKDAvWwjuGKdLKv4E7o1aXj5qaGg0ZMkTPPPPMBY+ZOHGiioqKmrZXXnmlXSEBAP7v7dzj+vsneZKkP90yRL2Tok1OBLO0unJOmjRJkyZNuugxVqtVKSkpbQ4FAAgsuwvt+vmbOyRJs8b0YiJpJ9chV7usXbtWSUlJys7O1v33368TJ05c8Fin0ymHw9FsAwAEjpM1dfrxS9tUW+/Wt/omas4N2WZHgsk8Xj4mTpyoF198UWvWrNHvf/97rVu3TpMmTZLL5Wrx+AULFshmszVtGRkZno4EADBJg8utB1/5XAUnTyszrov+ctvlXMUCWQzDaPPtAi0Wi5YtW6apU6de8JjDhw+rV69e+uCDD3T99def97jT6ZTT6Wz63uFwKCMjQ3a7XTExMW2NBgDwAb99b4/+9nGeIkKDtWzWVeqXwu/1QOVwOGSz2S7p87vDFxnr2bOnEhISdPDgwRYft1qtiomJabYBAPzfG9sK9LePGyeY/vH7gykeaNLh5aOgoEAnTpxQaiqTiwCgs9h2tEK/fGunJOknY3vrO4PTTE4EX9Lqq12qq6ubjWLk5eUpNzdXcXFxiouL0/z58zVt2jSlpKTo0KFD+tnPfqbevXtrwoQJHg0OAPBNhZWn9eOXtqvO5daEgcmaPa6v2ZHgY1pdPrZu3aoxY8Y0fT9nzhxJ0owZM7Rw4ULt2LFD//znP1VZWam0tDSNHz9ev/nNb2S1Wj2XGgDgk07VNejeF7eqvNqpfinReuKWoQpiginO0erycd111+lic1RXrVrVrkAAAP/kdht6+PUvtLvQofjIMP3vjCtYwRQt4q62AACP+NPqffq/ncUKDbbouTuHK71rF7MjwUdRPgAA7fba1nw989EhSdKCmwZrRI84kxPBl1E+AADt8tmh8qYrWx4Y01s3D083ORF8HeUDANBmh8qqdd9L29TgNvSdwamacwNXtuCbUT4AAG1SUVOnH76wRY7aBl2eGav//v4QrmzBJaF8AABa7XSdS//vn1t09MQppXeN0N/uukLhocFmx4KfoHwAAFrF5Tb006Wfa/uxSsWEh2jR3SOUEMVaTrh0lA8AwCUzDEPzV+zWv/aUKCw4SP87Y4T6JEebHQt+hvIBALhkz68/rBc3HJUk/fnWoRqZxSW1aD3KBwDgkryde1yPv79XkvSrG/vrxsHcMBRtQ/kAAHyjjw+U6eHXv5AkzbwmS//v2p4mJ4I/o3wAAC7qi/xK/filbap3GbpxcKr+89v9zY4EP0f5AABc0MHSat29aLNO1bl0Te8EPXELa3mg/SgfAIAWFdlP666/b9LJU/Uakm7Tc3cOlzWEtTzQfpQPAMB5TtbU6c6/b1ahvVY9EyP1j7tHKMoaYnYsBAjKBwCgmWpng+5+YYsOllYrJSZcL80cpXgWEYMHUT4AAE1q612a+cIWfZFfqa5dQvXSzJHqFhthdiwEGMoHAECSVNfg1n2Lt2lTXoWirSF68YejWL0UHYLyAQBQg8ut2a9+rrX7yhQeGqR/3DNCl6XbzI6FAEX5AIBOzu029Iu3dur/dhYrLDhIf7vrCo3owbLp6DiUDwDoxNxuQ/+5fJfe2Fag4CCLnv7B5bq2T6LZsRDgKB8A0EkZhqF57+zWK5uPKcgiPXHLEI0fmGJ2LHQClA8A6IQMw9D8FXv00sajslik//7+EE0Z2s3sWOgkKB8A0MkYhqHfvvelXvjsiCTp99MG66Zh6eaGQqdC+QCATsQwDD3+/l797yd5kqQFN12mW67IMDkVOhvWygWATsIwDD323pf6+5ni8ZupgzR9ZKbJqdAZUT4AoBP4ao7HV6dafjN1kO68sru5odBpUT4AIMC53YYeeWeXFm88JqnxVAsjHjAT5QMAAthX63i8svmYLJbGyaXM8YDZKB8AEKAaXG797I0deuvz4wo6czktV7XAF1A+ACAAORtc+ukruVq5u1jBQRY9cQvreMB3UD4AIMCcrnPpvsXbtG5/mcKCg/T0Dy5n5VL4FMoHAASQqtp6zfznVm3Oq1BEaLD+etdw7tUCn0P5AIAAUVFTp3sWbdYXBXZFW0P0j3tGcHda+CTKBwAEgOOVp3Xn3zfpcFmNunYJ1Ys/HKXL0m1mxwJaRPkAAD93oKRKd/59s4odtUqzhevFmaPUOynK7FjABVE+AMCPbT92Uj98YYsqT9Wrd1KUXvzhSKXFRpgdC7goygcA+KmP9pXq3xZv1+l6l4ZmxGrR3SPUNTLM7FjAN6J8AIAfenXLMf1y2S653Iau7ZOg5+4Yrkgrv9LhH/ibCgB+xDAMPfnBAT215oAk6aZh3fT4TYMVFhJkcjLg0lE+AMBP1Lvc+s9lO/Xa1gJJ0qwxvfTw+GxZLBaTkwGtQ/kAAD9QVVuvB5Z8rnX7yxRkkf5ryiDdcWV3s2MBbUL5AAAfd7zytGa+sEV7i6sUHhqk/5k+TDcMSDY7FtBmrT5JuH79ek2ePFlpaWmyWCxavnx5s8cNw9Ajjzyi1NRURUREaNy4cTpw4ICn8gJAp7KjoFJTn/lUe4urlBht1as/yqF4wO+1unzU1NRoyJAheuaZZ1p8/A9/+IP+8pe/6LnnntOmTZsUGRmpCRMmqLa2tt1hAaAzWbmrWLc8v0FlVU71S4nW8llXa0hGrNmxgHZr9WmXSZMmadKkSS0+ZhiGnnzySf3qV7/SlClTJEkvvviikpOTtXz5ct12223tSwsAnYBhGHpu3WH9YdVeGYb0rb6JevoHlys6PNTsaIBHePTarLy8PBUXF2vcuHFN+2w2m0aNGqUNGza0+DNOp1MOh6PZBgCdVW29S3Ne+0K/X9lYPO64MlN/n3EFxQMBxaPlo7i4WJKUnNz8fGRycnLTY+dasGCBbDZb05aRkeHJSADgN0odtbrtrxu17PPjCg6y6DdTBuqxqZcpJJg1PBBYTP8bPXfuXNnt9qYtPz/f7EgA4HU7C+z67tOfKje/UraIUL34w5G6M6eH2bGADuHRS21TUlIkSSUlJUpNTW3aX1JSoqFDh7b4M1arVVar1ZMxAMCvLPu8QL94c6ecDW71SozU32eMUI+ESLNjAR3GoyMfWVlZSklJ0Zo1a5r2ORwObdq0STk5OZ58KQDwe/Uut/5rxR499OoXcja4NSY7UctmXU3xQMBr9chHdXW1Dh482PR9Xl6ecnNzFRcXp8zMTM2ePVuPPfaY+vTpo6ysLP36179WWlqapk6d6sncAODXyqudmvXydm3Kq5AkPTi2t2aP66vgIJZKR+BrdfnYunWrxowZ0/T9nDlzJEkzZszQCy+8oJ/97GeqqanRj370I1VWVuqaa67RypUrFR4e7rnUAODHvsiv1P2Lt6nQXqvIsGD96ZahmjgoxexYgNdYDMMwzA5xNofDIZvNJrvdrpiYGLPjAIDHGIahxZuO6Tcr9qjO5VbPhEj99a7h6p0UbXY0oN1a8/nNvV0AwAtO1TXol2/t1PLcQknS+AHJ+u9bhiiG9TvQCVE+AKCDHSqr1v2Lt2l/SbWCgyz6+cRs3XttT1kszO9A50T5AIAO9Hbucf3yrZ2qqXMpMdqqp6dfrlE9482OBZiK8gEAHeB0nUuPvrNbr25tXDhxVFac/ucHlyspmsn3AOUDADzsQEmVZi3Zrv0l1bJYpAfH9tFPxvZmmXTgDMoHAHiIYRh6fWuBHnlnl2rr3UqIsuqp24bq6t4JZkcDfArlAwA8wH6qXr9ctlPv7SySJF3TO0F/vnWoEqO5fQRwLsoHALTTpsMn9NCruSq01yokyKI54/vqvtG9FMRqpUCLKB8A0Eb1Lrf+suaAnvnooNyG1CO+i5667XINyYg1Oxrg0ygfANAGB0urNee1XO0osEuSvj88XY9+d6AirfxaBb4J/y8BgAtwuQ1tzqtQaVWtkqLDNTIrThZJL244ogXv75WzwS1bRKh++71B+s7gNLPjAn6D8gEALVi5q0jzV+xRkb22aV9StFXxUWH6sqhKknRtnwT98eYhSrGxdgfQGpQPADjHyl1Fun/xdp17183SKqdKq5wKDbbo198ZoDuv7M4S6UAbsOINAJzF5TY0f8We84rH2WIjQnX7KIoH0FaUDwA4y+a8imanWlpSVl2nzXkVXkoEBB7KBwCcpbTq4sWjtccBOB/lAwDOcLsN5R6rvKRjuUEc0HZMOAUANa7b8Ys3d2jr0ZMXPc4iKcXWeNktgLZh5ANAp1Zb79ITq/fr2099rK1HTyoyLFi3jciQ1Fg0zvbV9/MmD1AwS6cDbcbIB4BO67OD5frP5buUV14jSRqTnajHvneZusVG6LrsxPPW+UixhWve5AGaOCjVrMhAQKB8AOh0yqud+t17X+qtz49Lalw87NHvDtSkQSlNl89OHJSqGwaknLfCKSMeQPtRPgB0Gi63oZc3HdV/r9onR22DLBbpziu76+EJ2YoJDz3v+OAgi3J6xZuQFAhslA8AncL2Yyf16+W7tLvQIUkamBajx6YO0uWZXU1OBnQ+lA8AAa282qk/rtynV7fmS5JiwkP0HxOy9YNR3TmFApiE8gEgINU1uPXihiN66oMDqnI2SJJuHp6uX0zqp4Qoq8npgM6N8gEg4KzdV6r/enePDpc1XsVyWTebHv3uAA3vztocgC+gfAAIGAdKqvS7//tSH+0rkyQlRIXpPyZk6/vDMxTEKRbAZ1A+APi98mqnnvxgv17ZnC+X21BIkEV3X9VDPxnXp8WrWACYi/IBwG/V1ru06NMjevajg03zOsYPSNYvJvVTz8Qok9MBuBDKBwC/43IbenN7gf68en/TCqSDusXoVzcO0JU9WZcD8HWUDwB+wzAMfbSvVL9/f5/2lVRJktJs4fr38dn63uXdmNcB+AnKBwC/sOVIhf64ap8251VIkmwRoZo1ppfuyumh8NBgk9MBaA3KBwCftuu4XX/6176mK1jCQoJ0z1U99G/X9ZatC5NJAX9E+QDgkw6WVunPHxzQezuKJDXeZ+XWERl6cGxvpdoiTE4HoD0oHwB8yqGyav1lzQG980WhDEOyWKQpQ9I0e1xf9UiINDseAA+gfADwCXnlNfqfNQe0PPe43EbjvgkDkzV7XF/1T40xNxwAj6J8ADDVgZIqPf3RQa34orCpdNwwIFmzx/XRwDSbueEAdAjKBwBT7C606+kPD2rl7mIZZ0rH9f2SNHtcX12WTukAAhnlA4BXbTlSoYVrD+nDvaVN+yYOTNEDY3trUDdKB9AZUD4AdLivFgdbuPaQthw5KUkKskg3Dk7TA2N6Kzsl2uSEALyJ8gGgw9Q1uLXii0L97ePD2lvcuCJpWHCQpg3vph+P7sXVK0AnRfkA4HGO2nq9sumYFn16RMWOxnuvRIYF6/Yru2vmNVlKjgk3OSEAM1E+AHhMfsUpvfDZEb26JV/VZ+4ymxht1T1X99DtI7uzIikASR1QPh599FHNnz+/2b7s7Gzt3bvX0y8FwAcYhqEtR07q758c1uo9JU2Xy/ZJitK9o3tqytA0WUO49wqAr3XIyMfAgQP1wQcffP0iIQywAIGmtt6lFV8U6p8bjmjXcUfT/mv7JOiH12TpW30SucssgBZ1SCsICQlRSkpKRzw1AJMdrzytxRuPaunmYzp5ql6SZA0J0k3Duumeq7PUN5krVwBcXIeUjwMHDigtLU3h4eHKycnRggULlJmZ2eKxTqdTTqez6XuHw9HicQDM43Yb+uRguRZvPKoPvvz61EqaLVx35HTXbSMyFRcZZm5IAH7DYhhfrS3oGe+//76qq6uVnZ2toqIizZ8/X8ePH9euXbsUHX3+v4hamiMiSXa7XTEx3M8BMFNFTZ1e35qvJZuP6eiJU037c3rGa8ZVPTSuf5JCgoNMTAjAVzgcDtlstkv6/PZ4+ThXZWWlunfvrieeeEIzZ8487/GWRj4yMjIoH4BJDMPQhsMn9MrmfK3aVaw6l1uSFG0N0bTh6bp9VKb6cGoFwDlaUz46fCZobGys+vbtq4MHD7b4uNVqldVq7egYAL5BaVWt3tx2XK9uOaYjZ41yDOoWoztGddd3h6apSxiTxwG0X4f/JqmurtahQ4d05513dvRLAWilepdbH+0t1WtbC/TRvlK5zkzmiLKG6LtD0zR9RCY3eQPgcR4vHw8//LAmT56s7t27q7CwUPPmzVNwcLCmT5/u6ZcC0Eb7iqv05vYCvbW9QOXVdU37L8+M1fQRmbpxcKoirYxyAOgYHv/tUlBQoOnTp+vEiRNKTEzUNddco40bNyoxMdHTLwWgFcqrnXont1Bvbi/Q7sKvrypLiLJq2rBu+v4V6eqdxFwOAB3P4+Vj6dKlnn5KAOdwuQ1tzqtQaVWtkqLDNTIrTsEtLOh1us6lf+0p1tu5hVq/v0wNZ06rhAZbNLZfkqYNS9eYfkkK5YoVAF7EuCrgZ1buKtL8FXtUZK9t2pdqC9e8yQM0cVCqGlxufXrohN7+/LhW7i7WqTpX03FDMmI1bVg3TR6cpq6sywHAJJQPwI+s3FWk+xdv17nXxxfZa3Xf4u0a3TdBu447VFHz9TyOzLgumjI0TVOGdlPvpCjvBgaAFlA+AD/hchuav2LPecXjbOv3l0uS4iLD9J3BqZoytJuGZcbKYuEeKwB8B+UD8BOb8yqanWq5kLmT+mnmNVmsPArAZ1E+AB9X73Jr0+EKLVzX8kJ950qxhVM8APg0ygfgg07VNWj9/nKt3lOiD74skf10/SX/bFJ0eAcmA4D2o3wAPqKsyqkP95Zo9Z4SfXygXM4Gd9Nj8ZFhGjcgWf/aXdx0G/tzWdQ46jEyK85LiQGgbSgfgEkMw9CXRVVa82WJPthbqi/yK5s9nhEXoRv6p2j8wGSN6NG4jseY7ETdv3h748+fdexX00nnTR7Q4nofAOBLKB+AF9U4G/TpwXJ9tK9Ma/eVnjeB9LJuNt0wIFnjByYrOzn6vKtUJg5K1cI7hp23zkfKWet8AICvo3wAHcgwDO0vqda6/aVat79Mm/MqVO/6eswiPDRI1/RO1Lj+SRrTL0nJMd88X2PioFTdMCDlklY4BQBfRPkAPOxkTZ0+PVSu9fvLtH5/uYodzUc3MuO6aGy/JF2Xnagre8YrPDS41a8RHGRRTq94T0UGAK+ifADtVFvv0vajJ/XxwXJ9cqBcuwrtMs6akGENCdKVPeM1um+ixmQnKishkkW/AHRqlA+glRpcbu0qdOjTg+X67FC5th452ezKFEnKTo7WtX0SNLpvokZmxbVpdAMAAhXlA/gGLrehPYUObTx8QhsPn9DmvApVORuaHZMYbdW1vRN0TZ8EXdM7QUmXMHcDADorygdwjnqXW7uO27U5r6JxO1KhqtrmZSMmPEQ5veJ1Va8EXd07Xr0SoziVAgCXiPKBTq/G2aDc/EptPXJSW45UaNvRkzpd72p2TLQ1RCOz4pTTK16jsuI1IC2Gq0sAoI0oH+h0iuynte3oyaZtd6FDLnfze8XGdgnViB5xGpUVp5FZcRqYZqNsAICHUD4Q0JwNLu0udOjzY5X6/NhJbT96UoUt3Bm2W2yEhnfvqit6dNWorHj1SYpSEGUDADoE5QMBwzAMHTlxSl/kVyr3zLan0KE6V/MrUYKDLOqfGq1hmV3PFI44dYuNMCk1AHQ+lA/4JcMwVOyo1Y4Cu3YW2PVFQaV2FNhbvPtrXGSYLs+I1eWZsRrWvauGpMcq0spffQAwC7+B4fMMw1CRvVa7jtsbt0KHdhTYVV7tPO/YsJAgDUyL0ZD0WA3NiNWwzK7KiIvgShQA8CGUD3iUy220654jLrehIydqtLvQod2Fdu0pdGhPoUMnaurOOzY4yKI+SVEanG7TZemxGpoeq+yUaIWFBHnyPwkA4GGUD3jMyl1F591tNfUid1utqq3X3uIq7S1yaE9Rlb4scmhfcdV5l7lKUkiQRX2SozUoLUYD02I0OCNWA1JjWDkUAPwQ5QMesXJXke5fvF3GOfuL7bW6b/F2/fo7/ZUYHa59xQ7tLarS3uIqHa883eJzRYQGq19qtAamxWhAqk0D02KUnRJN0QCAAEH5QLu53Ibmr9hzXvGQ1LTvN+9+2eLPpsSEq39qtPqnxjRtWQmRrKkBAAGM8oFWO1XXoMNlNTpUVq2DpdXalFfR7FTLhfRJitIVPeLUPzVa2cnRyk6JVmyXMC8kBgD4EsoHWuR2Gyq0n1ZeeY0Ol9XocFm1Dp35s6VFui7FA2N7a8rQbh5OCgDwN5SPTswwDJU4nDpyokZHymuUd+bPI+WnlHeiRnXn3Cb+bHGRYeqdGKVeSVEKCbLopY1Hv/H1kqK50ysAgPIR8Ooa3DpeeVrHKk7pWMUpHS2v0dGKUzp24pSOVtSotv7CBSM02KLu8ZHKSohUz8RI9UqMUq/ESPVMiFLXyK9Pl7jchj74skTF9toW531YJKXYGi+7BQCA8uHn3G5DZdVO5VecUv7JU8qvON3s6yL7ablbagRnBAdZlN41Qj3iI9Ujvot6JJwpGwlRSosNV0jwN6+ZERxk0bzJA3T/4u2ySM0KyFfTRudNHsAkUgCAJMqHz6t3uVVsr9XxytM6fvJ0sz8LTp5SYWXtefcuOVd4aJAy47qc2SLVI6Hx6x7xkerWNUKhl1AwvsnEQalaeMew89b5SLnIOh8AgM6p05SP9q682RHcbkPl1U4V2WtVZD+twspaFTsai0ZRZeP3JVW1Mi4yciE1jjykxIQrIy5CGV27KCOuS9PXmfFdlBhl9cry4hMHpeqGASk+9z4DAHxLpygfrV150xNq610qdThV7GgsFCX22qavi+2NW4mjVg0XOydyRlhwkNJiw9Wta4TSbBHq1jVC3WIjlBHXReldI5QSc2mnR7whOMiinF7xZscAAPiwgC8fF1t58/7F27XwjmGtKiA1zgaVVTlVWuVUaVWtSh3nfl2rEoezxburtiTI0ngVSIotXGmx4Uq1RSjVFq5usRFKO7PFR4YpiNEDAECACOjy8U0rb1okPfrObuX0SlDlqTqVVztVVtX4Z9N25vuyaqfKqpw6VXf+fUcuxBoSpBRbuJJjwpUSE970daqt8euUmHAlRls9MucCAAB/EdDlY/M3rLxpSCp2ODVk/r9a9bwRocFKirEqKdqqpOjGApEUY1VydGO5SI6xKikmXDHhIdzKHQCAcwR0+SituvSVOCNCg5UQHab4SKsSosKUGG1VQtTXW1KMVYlRViVGWxVpDei3DQCADhXQn6KXuqLmortHaEy/pA5OAwAAJCmgJxuMzIpTqi1cFzrxYVHjVS+j+yZ6MxYAAJ1aQJePr1belHReAWHlTQAAzBHQ5UP6euXNFFvzUzAptvBWX2YLAADaL6DnfHyFlTcBAPAdnaJ8SKy8CQCAr+iw0y7PPPOMevToofDwcI0aNUqbN2/uqJcCAAB+pEPKx6uvvqo5c+Zo3rx52r59u4YMGaIJEyaotLS0I14OAAD4kQ4pH0888YTuvfde3XPPPRowYICee+45denSRf/4xz864uUAAIAf8Xj5qKur07Zt2zRu3LivXyQoSOPGjdOGDRvOO97pdMrhcDTbAABA4PJ4+SgvL5fL5VJycnKz/cnJySouLj7v+AULFshmszVtGRkZno4EAAB8iOnrfMydO1d2u71py8/PNzsSAADoQB6/1DYhIUHBwcEqKSlptr+kpEQpKSnnHW+1WmW1Wj0dAwAA+CiPj3yEhYVp+PDhWrNmTdM+t9utNWvWKCcnx9MvBwAA/EyHLDI2Z84czZgxQ1dccYVGjhypJ598UjU1Nbrnnns64uUAAIAf6ZDyceutt6qsrEyPPPKIiouLNXToUK1cufK8SagtMQxDkrjqBQAAP/LV5/ZXn+MXYzEu5SgvKigo4IoXAAD8VH5+vtLT0y96jM+VD7fbrcLCQkVHR8ti8eyN3xwOhzIyMpSfn6+YmBiPPje+xvvsHbzP3sH77D28197RUe+zYRiqqqpSWlqagoIuPqXU524sFxQU9I2Nqb1iYmL4i+0FvM/ewfvsHbzP3sN77R0d8T7bbLZLOs70dT4AAEDnQvkAAABe1anKh9Vq1bx581jUrIPxPnsH77N38D57D++1d/jC++xzE04BAEBg61QjHwAAwHyUDwAA4FWUDwAA4FWUDwAA4FWdpnw888wz6tGjh8LDwzVq1Cht3rzZ7EgBZ/369Zo8ebLS0tJksVi0fPlysyMFpAULFmjEiBGKjo5WUlKSpk6dqn379pkdK+AsXLhQgwcPblqIKScnR++//77ZsQLe448/LovFotmzZ5sdJaA8+uijslgszbZ+/fqZlqdTlI9XX31Vc+bM0bx587R9+3YNGTJEEyZMUGlpqdnRAkpNTY2GDBmiZ555xuwoAW3dunWaNWuWNm7cqNWrV6u+vl7jx49XTU2N2dECSnp6uh5//HFt27ZNW7du1dixYzVlyhTt3r3b7GgBa8uWLXr++ec1ePBgs6MEpIEDB6qoqKhp++STT0zL0ikutR01apRGjBihp59+WlLj/WMyMjL04IMP6he/+IXJ6QKTxWLRsmXLNHXqVLOjBLyysjIlJSVp3bp1Gj16tNlxAlpcXJz++Mc/aubMmWZHCTjV1dUaNmyYnn32WT322GMaOnSonnzySbNjBYxHH31Uy5cvV25urtlRJHWCkY+6ujpt27ZN48aNa9oXFBSkcePGacOGDSYmAzzDbrdLavxgRMdwuVxaunSpampqlJOTY3acgDRr1izdeOONzX5Xw7MOHDigtLQ09ezZU7fffruOHTtmWhafu7Gcp5WXl8vlcik5ObnZ/uTkZO3du9ekVIBnuN1uzZ49W1dffbUGDRpkdpyAs3PnTuXk5Ki2tlZRUVFatmyZBgwYYHasgLN06VJt375dW7ZsMTtKwBo1apReeOEFZWdnq6ioSPPnz9e1116rXbt2KTo62ut5Ar58AIFs1qxZ2rVrl6nnbgNZdna2cnNzZbfb9cYbb2jGjBlat24dBcSD8vPz9dOf/lSrV69WeHi42XEC1qRJk5q+Hjx4sEaNGqXu3bvrtddeM+U0YsCXj4SEBAUHB6ukpKTZ/pKSEqWkpJiUCmi/Bx54QO+++67Wr1+v9PR0s+MEpLCwMPXu3VuSNHz4cG3ZskVPPfWUnn/+eZOTBY5t27aptLRUw4YNa9rncrm0fv16Pf3003I6nQoODjYxYWCKjY1V3759dfDgQVNeP+DnfISFhWn48OFas2ZN0z632601a9Zw7hZ+yTAMPfDAA1q2bJk+/PBDZWVlmR2p03C73XI6nWbHCCjXX3+9du7cqdzc3Kbtiiuu0O23367c3FyKRweprq7WoUOHlJqaasrrB/zIhyTNmTNHM2bM0BVXXKGRI0fqySefVE1Nje655x6zowWU6urqZi06Ly9Pubm5iouLU2ZmponJAsusWbO0ZMkSvf3224qOjlZxcbEkyWazKSIiwuR0gWPu3LmaNGmSMjMzVVVVpSVLlmjt2rVatWqV2dECSnR09HnzlSIjIxUfH888Jg96+OGHNXnyZHXv3l2FhYWaN2+egoODNX36dFPydIryceutt6qsrEyPPPKIiouLNXToUK1cufK8Sahon61bt2rMmDFN38+ZM0eSNGPGDL3wwgsmpQo8CxculCRdd911zfYvWrRId999t/cDBajS0lLdddddKioqks1m0+DBg7Vq1SrdcMMNZkcDWq2goEDTp0/XiRMnlJiYqGuuuUYbN25UYmKiKXk6xTofAADAdwT8nA8AAOBbKB8AAMCrKB8AAMCrKB8AAMCrKB8AAMCrKB8AAMCrKB8AAMCrKB8AAMCrKB8AAMCrKB8AAMCrKB8AAMCrKB8AAMCr/j8nl8s9v7F63AAAAABJRU5ErkJggg==\n" }, "metadata": {} } ] }, { "cell_type": "markdown", "source": [ "These look spot on! How would we go about converting something that maybe is not so simple or well known? We guess that the solution is $f(x) = c a^x$ and plug it in and see if we can solve for $a$ ($c$ will just drop out most of the time so I'll forget about it until I ask for initial conditions)\n", "\n", "$$f(n+1) = 2f(n)$$\n", "\n", "$$ca^{n+1} = 2ca^{n}$$\n", "\n", "Divide by $ca^n$ and get\n", "\n", "$$a = 2$$" ], "metadata": { "id": "OhPY-ilSD9hO" } }, { "cell_type": "markdown", "source": [ "## Something More Exotic\n", "\n", "What is we had a recurrance relaionship of the form\n", "$$\n", "f(n) = -3f(n-1)+4f(n-2)\n", "$$\n", "Beacause there are two prior steps, our initial condition will need two parts.\n", "$$\n", "f(0) = 1\\quad\\quad f(1) =2\n", "$$\n", "\n", "We can of course define it via python recursively:" ], "metadata": { "id": "44ZFJfXzHC-g" } }, { "cell_type": "code", "source": [ "def f(n):\n", " if n>1:\n", " return -3*f(n-1)+4*f(n-2)\n", " if n==1:\n", " return 2\n", " if n==0:\n", " return 1\n", "\n", "[f(i) for i in range(10)]" ], "metadata": { "id": "Q4hBSvy6DniT", "colab": { "base_uri": "https://localhost:8080/" }, "outputId": "bde6bb8a-b34c-4cbc-c012-e2ea3e970444" }, "execution_count": null, "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "[1, 2, -2, 14, -50, 206, -818, 3278, -13106, 52430]" ] }, "metadata": {}, "execution_count": 7 } ] }, { "cell_type": "markdown", "source": [ "How could we get an analytic solution for this? Let's guess that the solution is $f(n) = r^n$. Plugging this into our reccurance relation, we see that,\n", "$$\n", "r^n = 3r^{n-1} -4r^{n-2}\n", "$$\n", "\n", "With some algebra, we see that\n", "$$\n", "0= r^n+3r^{n-1}-4r^{n-2} = r^{n-2}\\left(r^2+3r-4\\right) = r^{n-2}(r+4)(r-1)\n", "$$\n", "\n", "So we see that either $r=0$ (trivial solution and doesn't work with our initial conditions) or $r=-4$ or $r=1$.\n", "\n", "To finish then, we utilize our initial conditions and recall tha I should have used $f(n) = c r^n$. We arrive at\n", "$$\n", "f(n) = c_1(-4)^n+c_21^n\\\\\n", "f(0) = c_1+c_2 = 1\\\\\n", "f(1) = -4c_1 +c_2 = 2\n", "$$\n", "\n", "Solving the above system for $c_1$ and $c_2$ we see that $c_1 = -\\frac15$ and $c_2 = \\frac65$. \n", "\n", "Putting it all together\n", "\n", "$$\n", "f(n) = -\\frac15(-4)^n+\\frac65 1^n\n", "$$\n", "\n", "We define this function with python" ], "metadata": { "id": "f4RLKdETIdV8" } }, { "cell_type": "code", "source": [ "def f(x):\n", " return -1/5*(-4)**x+6/5\n", "\n", "[f(i) for i in range(10)]" ], "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "Hc5FmQeCLQVH", "outputId": "a015488b-fe21-4d51-b1f8-86ecef04cb1d" }, "execution_count": null, "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "[1.0, 2.0, -2.0, 14.0, -50.0, 206.0, -818.0, 3278.0, -13106.0, 52430.0]" ] }, "metadata": {}, "execution_count": 8 } ] }, { "cell_type": "markdown", "source": [ "## Repeated Roots" ], "metadata": { "id": "HrljN2BGJh1o" } }, { "cell_type": "markdown", "source": [ "If you happen to get a repeated root, you can still use this method except that the solution will be of the form,\n", "$$\n", "f(n) = c_1r^n+c_2nr^n\n", "$$\n", "The extra $n$ in the second term will account for the repeated root. Let's see this in play with an example:" ], "metadata": { "id": "xkylEJXgJk6B" } }, { "cell_type": "markdown", "source": [ "### Example\n", "Solve\n", "$$\n", "f(n) = 4f(n-1)-4f(n-2) \\quad\\quad f(0) =f(1) = 1\n", "$$\n", "\n", "We rewrite into the form as discussed above:\n", "$$\n", "r^n = 4r^{n-1}-4r^{n-2}\n", "$$\n", "Apply a little agebraic magic to get\n", "$$\n", "r^n-4r^{n-1}+4r^{n-2} = r^{n-2}(r^2-4r+4) = r^{n-2}(r-2)^2\n", "$$\n", "So $r=2$ is a solution and repeated!\n", "\n", "Using the form discussed above, we see that\n", "$$\n", "f(n) = c_12^n+c_2n2^n\n", "$$\n", "We apply the initial conditions to solve for $c_1$ and $c_2$.\n", "$$f(0) = 1 = c_1$$\n", "$$f(1) = 1 = 2c_1+2c_2$$\n", "So $c_1 = 1$ and $c_2 = -\\frac12$. Making\n", "$$\n", "f(n) = 2^n-\\frac{n}2 2^n\n", "$$\n", "Let's test these solutions." ], "metadata": { "id": "1Nm-tdpvKGjD" } }, { "cell_type": "code", "source": [ "def f(n):\n", " if n==0:\n", " return 1\n", " elif n==1:\n", " return 1\n", " else:\n", " return 4*f(n-1)-4*f(n-2)\n", "\n", "[f(i) for i in range(10)]" ], "metadata": { "id": "FKhEPFNsL6V1", "outputId": "3c9f8d64-f531-4fca-b269-d6512e2dbf1c", "colab": { "base_uri": "https://localhost:8080/" } }, "execution_count": 2, "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "[1, 1, 0, -4, -16, -48, -128, -320, -768, -1792]" ] }, "metadata": {}, "execution_count": 2 } ] }, { "cell_type": "code", "source": [ "def f(x):\n", " return 2**x-x/2*2**x\n", "\n", "[f(i) for i in range(10)]" ], "metadata": { "id": "IoxtTsq_MPF8", "outputId": "743d9b9c-765c-4dc2-8eeb-3beaa9328a93", "colab": { "base_uri": "https://localhost:8080/" } }, "execution_count": 3, "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "[1.0, 1.0, 0.0, -4.0, -16.0, -48.0, -128.0, -320.0, -768.0, -1792.0]" ] }, "metadata": {}, "execution_count": 3 } ] }, { "cell_type": "markdown", "source": [ "## Non-Homogeneous\n", "\n", "Thus fas all of the recursive functions we have dealt with had only factors invloving the function before. Often this will not be the case. When we have a term that is not recursively defined, we will attempt to use a function that is of the same form as our term. We will have to use some _undetermined coefficients_ to fully solve the problem. Let's see this in action" ], "metadata": { "id": "HDPu9NUqMcsN" } }, { "cell_type": "markdown", "source": [ "### Example\n", "$$\n", "f(n) = -3f(n-1)+4f(n-2) +5^n\n", "\\quad\n", "f(0) = 1\\quad\\quad f(1) =2\n", "$$\n", "\n", "This is the same recurance relation that we examined before. The homogeneous part of the solution will stay the same.\n", "$$\n", "f_H(n) = c_1(-4)^n+c_21^n\n", "$$\n", "We make a guess at the particular solution\n", "$$\n", "f_P(n) = a5^n\n", "$$\n", "We see what happens when we plug this into the original equation.\n", "$$\n", "a5^n = -3a5^{n-1}+4a5^{n-2}+5^n\n", "$$\n", "We want to find what $a$ solves the above equation. Rearranging we see that\n", "$$\n", "0=(a-1)5^n +3a5^{n-1}-4a5^{n-2} = 5^{n-2}((a-1)5^2 +3a5-4a) = 5^{n-2}\\left(25a-25+15a-4a\\right) = 5^{n-2}\\left(36a-25\\right)\n", "$$\n", "So to solve this equation $a = \\frac{25}{36}$.\n", "\n", "To get the full solution, we combine the homogeneous and particular solution\n", "$$\n", "f(n) = f_H(n) +f_P(n) = c_1(-4)^n+c_2+\\frac{25}{36} 5^n\n", "$$\n", "We now solve for the initial conditions.\n", "$$\n", "f(0) = 1 = c_1+c_2+\\frac{25}{36}\n", "$$\n", "and\n", "$$\n", "f(1) = 2 = -4c_1+c_2+\\frac{125}{36}\n", "$$\n", "\n", "After some work, I arrive at $c_1 = \\frac{16}{45}$ and $c_2 = -\\frac1{20}$\n", "\n", "So the full solution is\n", "$$\n", "f(n) = \\frac{16}{45}(-4)^n-\\frac1{20}+\\frac{25}{36}5^n\n", "$$" ], "metadata": { "id": "kTRkKtSvNJdc" } }, { "cell_type": "markdown", "source": [ "### Forms for the Non Homogeneous Part\n", "\n", "|Equation|Form of the Non-Homogeneous Part with undetermined coefficients|\n", "|-------|---------------------------------------------------------------------|\n", "|Polynomial|$f_P = an^x+bn^{x-1}+cn^{x-2}+\\cdots gn+f$|\n", "|Exponential with base $a$ | $f_P = ca^n$|\n", "|Sine and Cosine| $f_P = a\\sin n+ b\\cos n$|\n" ], "metadata": { "id": "1K4slwc8Rd7O" } }, { "cell_type": "markdown", "source": [ "##References\n", "\n", "____Discrete Math____ https://discrete.openmathbooks.org/dmoi3/dmoi.html by Oscar Levin\n", "\n", "___Python Programming and Numerical Methods___ https://pythonnumericalmethods.berkeley.edu/notebooks/Index.html\n" ], "metadata": { "id": "84b69rIBXkSy" } } ] }