Recurrences using Programming !!!!

It's possible to generalize many of the recurrence relations (that we come across in Combinatorics problems, (you may want to try recurrence relations problems like these )

To learn how to generalize recurrence relations (using math) you could read these notes by Daniel Chiu - recursion, linear, part 2.

And if you want to know some tricks to manipulate things come to homogeneous recurrences, see the solutions in my note Need help

This was for in Maths... Let's now try programming..... (I have just started learning it...)

1. The famous Fibonacci sequence.... It is defined as $a_0=0$, $a_1=1$ and for $n\geq 2$ $a_n = a_{n-1} + a_{n-2}$

In programming(Python), people try various programs to print the numbers, but what i prefer is , start with an empty list "$\color{#D61F06}{\textbf{ li=[ ] }}$ "

Then, we write a program which will take into consideration all the Fibonacci numbers.

recurnce

As shown in the image, just $\color{#D61F06}{\textbf{append}}$ the $b$ to $\color{#D61F06}{\textbf{li}}$ , so the $\color{#D61F06}{\textbf{list "li"}}$ is now containing the terms of Fibonacci Sequence!!!

On this list, as shown you can do operations like $sum$ of elements (use sum(li) ), $number$ of elements (use len(li), which gives length of list 'li'), and the $li.count$ code can be used to see whether any given number is a term of a Fibonacci sequence or not. (If the number is in Fibonacci sequence, then $\color{#D61F06}{\text{ li.count(number)}}$ will give value 1, and else, 0 )

This will be for the terms of Fibonacci sequence which are less than the range you type at first. (in the while loop)

Also, not only Fibonacci sequence, you can get other recurrence relations by this too !

Like the one in $3$ terms , like initial conditions $a_0=0,a_1=2,a_2=4$ and for $n\geq 3$, $a_n=7a_{n-1}+8a_{n-2}-4a_{n-3}$ This type of recurrences, you can solve by making characteristic equation and finding it's roots, as done in this note.

But by programming, it will be as follows

recrnc

In this one, the recurrence is simply defined by the last line in the loop. Then, the list will directly get numbers included and you can try any operations, like sum of first $n$ terms, or you can even find the $n^{th}$ term of the sequence just by using python code $\color{#D61F06}{\text{ li [n : (n+1) ]}}$ and it will give you the $n^{th}$ term. (Note that it won't give general form, it will give value for value of $n$ ).

Because this was example, i restricted the range of $c$ , but you may try to get bigger values by increasing it !

This shows the use of Programming to get terms of a recurrence relation and easily doing operations on them, like addition of few, for example, if you want the sum of terms $F_{3}$ to $F_7$ of Fibonacci sequence (i.e. $\displaystyle \sum_{n=3}^7 F_n$ , where $F_n$ is Finbonacci $n^{th}$ term), then you define a new list as $\color{#D61F06}{\textbf{li\_1 = li[2:7] }}$ and it will make $\color{#D61F06}{\textbf{li\_1}}$ to be list of Fibonacci numbers from $F_3$ to $F_7$. (Note that in new list, we took $2$ in formula for li_1 because it will exclude 2nd term)

Like and reshare if it was helpful to you.