How it Works › Forums › Introductory Problems (AMC 8 Problems 1020) › Recursion Introductory Problems!
 This topic has 2 replies, 2 voices, and was last updated 2 years, 11 months ago by Ayush Agarwal.

AuthorPosts

adminKeymaster
MathJax TeX Test Page
Hey Math Circle Students!Here are the introductory problems for the next $3$ days! These will give you a good idea about how recursive sequences work but will not go into their applications to combinatorics. If you don’t understand one of the questions, feel free to post in the questions forum here
1. Find the pattern or closed form (simple formula in terms of $n$) that satisfy the following recursive relations:
(a) $A_n=3A_{n1}$ where $A_1=1$
(b) $A_n=A_{n1}+5$ where $A_1=1$
(c) $A_n=A_{n2}+A_{n3}$ where $A_1=A_2=1$2. Consider the Fibonacci sequence $1,1,2,3,5,8,13,21,34…$ and consider each term’s remainder when divided by $3$. For example, if we divide by $2$ we have remainders: $1,1,0,1,1,0,1,1,0..$ and we see the pattern $1,1,0$ come up over and over again. Does this work if we consider the remainders when divided by $3$.
3. Define a sequence $B_n = n \times B_{n−1}$ where $B_0 = 1$. Find $B_1, B_2, B_3 … $. and find a closed form for $B_n$.
Remember that you can post your solutions below to these problems and I will keep a running leaderboards for the top 10 students who participate the most! I especially appreciate the same problem being solved in different ways!
AntonGuest1.
(a) 1, 3, 9 = powers of 3
A_n = 3^(n1)(b)Arithmetic sequence 1, 6, 11…
A_n = 5n – 4(c)We can’t find A_3 without setting A_0 = 0, right?
2. Fibonnaci sequence remainder 3 is: 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2…
This pattern repeats  3. B_0 = 1, B_1 = 1, B_2 = 2, B_3 = 6
B_n = n!Ayush AgarwalGuestGreat job Anton! Yes good note, that was my error, it is important to assume that a_0=0.
Since you got all of them right, I recommend you look at the advanced and exploration problems! 
AuthorPosts