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 a0=0a_0=0, a1=1a_1=1 and for n2n\geq 2 an=an1+an2a_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 " li=[ ] \color{#D61F06}{\textbf{ li=[ ] }} "

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

recurnce recurnce

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

On this list, as shown you can do operations like sumsum of elements (use sum(li) ), numbernumber of elements (use len(li), which gives length of list 'li'), and the li.countli.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  li.count(number)\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 33 terms , like initial conditions a0=0,a1=2,a2=4a_0=0,a_1=2,a_2=4 and for n3n\geq 3, an=7an1+8an24an3a_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 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 nn terms, or you can even find the nthn^{th} term of the sequence just by using python code  li [n : (n+1) ]\color{#D61F06}{\text{ li [n : (n+1) ]}} and it will give you the nthn^{th} term. (Note that it won't give general form, it will give value for value of nn ).

Because this was example, i restricted the range of cc , 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 F3F_{3} to F7F_7 of Fibonacci sequence (i.e. n=37Fn\displaystyle \sum_{n=3}^7 F_n , where FnF_n is Finbonacci nthn^{th} term), then you define a new list as li_1 = li[2:7] \color{#D61F06}{\textbf{li\_1 = li[2:7] }} and it will make li_1\color{#D61F06}{\textbf{li\_1}} to be list of Fibonacci numbers from F3F_3 to F7F_7. (Note that in new list, we took 22 in formula for li_1 because it will exclude 2nd term)


Like and reshare if it was helpful to you.

Note by Aditya Raut
5 years ago

No vote yet
1 vote

</code>...<code></code> ... <code>.">   Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in </span>...<span></span> ... <span> or </span>...<span></span> ... <span> to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Very good discovery. This is fundamental to programming theory.

Cody Johnson - 5 years ago

Log in to reply

??? trolling or what ? I know you already know this all....

Aditya Raut - 5 years ago

Log in to reply

The notes were by Daniel Chiu, not me. I fixed it for you ;)

Daniel Liu - 5 years ago

Log in to reply

@Daniel Liu Oops LOL

Aditya Raut - 5 years ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...