{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "### Example 2.4 (Virahanka-Fibonacci Numbers)\n", "A short investigation of the Virahanka-Fibonacci Numbers. Additional details on C-finite sequences in Sage can be found in the [documentation](https://doc.sagemath.org/html/en/reference/combinat/sage/rings/cfinite_sequence.html). \n", "*Requirements: None*" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The ring of C-Finite sequences in z over Rational Field\n" ] } ], "source": [ "# Define the ring of C-finite sequences over the rationals\n", "C. = CFiniteSequences(QQ)\n", "print(C)" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "C-finite sequence, generated by -1/(z^2 + z - 1)" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# C-finite sequences can be defined by their recurrence and initial conditions\n", "fib = C.from_recurrence([1,1],[1,1]) # Recurrence v_{n+2} = v_{n+1} + v_n with v_0 = v_1 = 1\n", "fib" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "C-finite sequence, generated by -1/(z^2 + z - 1)\n", "True\n" ] } ], "source": [ "# C-finite sequences can also be defined by their rational generating function\n", "fib2 = C('1/(1-z-z^2)')\n", "print(fib2)\n", "print(fib==fib2)" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1 + x + 2*x^2 + 3*x^3 + 5*x^4 + 8*x^5 + 13*x^6 + 21*x^7 + 34*x^8 + 55*x^9 + O(x^10)" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Series truncations can be computed from the sequence\n", "fib.series(10)" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]\n", "70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501\n" ] } ], "source": [ "# Sequence terms can also be accessed directly\n", "print([fib[k] for k in range(10)])\n", "print(fib[1000])" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "\\begin{math}\n", "\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\frac{1}{2} \\, {\\left(\\frac{1}{2} \\, \\sqrt{5} + \\frac{1}{2}\\right)}^{n} {\\left(\\sqrt{\\frac{1}{5}} + 1\\right)} - \\frac{1}{2} \\, {\\left(-\\frac{1}{2} \\, \\sqrt{5} + \\frac{1}{2}\\right)}^{n} {\\left(\\sqrt{\\frac{1}{5}} - 1\\right)}\n", "\\end{math}" ], "text/plain": [ "1/2*(1/2*sqrt(5) + 1/2)^n*(sqrt(1/5) + 1) - 1/2*(-1/2*sqrt(5) + 1/2)^n*(sqrt(1/5) - 1)" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Sage can find the closed form of the sequence (corresponding to Theorem 2.3 in the textbook)\n", "show(fib.closed_form())" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "C-finite sequence, generated by -1/(x^2 + x - 1)" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Sage can also guess a C-recurrence from a list of initial values\n", "C.guess([1,1,2,3,5,8])" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "SageMath 9.2", "language": "sage", "name": "sagemath" }, "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.8.5" } }, "nbformat": 4, "nbformat_minor": 4 }