Recursion - AMC 10B, 2019 Problem 25

What is Recursion

Recursion is basically an idea of connecting any term with the next or previous term of an series. The most famous example of recursion is Fibonacci series \(0,1,1,2,3,5,8,........\) its recursion formula is \(t_{n+2}=t_{n+1}+t_n\) for natural number n.

Try the problem

How many sequences of $0$s and $1$s of length $19$ are there that begin with a $0$, end with a $0$, contain no two consecutive $0$s, and contain no three consecutive $1$s?

$\textbf{(A) }55\qquad\textbf{(B) }60\qquad\textbf{(C) }65\qquad\textbf{(D) }70\qquad\textbf{(E) }75$

AMC 10B, 2019 Problem 25

Recursion

6 out of 10

challenges and thrills of pre college mathematics

Knowledge Graph

Recursion- knowledge graph

Use some hints

We can deduce, from the given restrictions, that any valid sequence of length $n$ will start with a $0$ followed by either $10$ or $110$. Thus we can define a recursive function $f(n) = f(n-3) + f(n-2)$, where $f(n)$ is the number of valid sequences of length $n$.

This is because for any valid sequence of length $n$, you can append either $10$ or $110$ and the resulting sequence will still satisfy the given conditions.

It is easy to find $f(5) = 1$ with the only possible sequence being $01010$ and $f(6) = 2$ with the only two possible sequences being $011010$ and $010110$ by hand, and then by the recursive formula, we have \(f(19)=65\) so option C is correct option.

Other useful links

Related Program

Math Olympiad

I.S.I. & C.M.I. Entrance Program

Taught by students and alumni of I.S.I. & C.M.I.

Learn More

Subscribe to Cheenta at Youtube

Consecutive terms of a series, B. Stat Hons., 2003 Problem-1

Comparing consecutive terms of a series

The question is based upon sequence and finding the relation between consecutive terms of a series with its next or previous term if the expression of its nth term is given.

Try the problem

Let \(a_n = \frac{{10^{n+1}+1}}{10^n +1}\), for \(n=1,2,3......\) . Then

(A) for every \(n, a_n \geq a_{n+1} ;\)

(B) for every \(n, a_n \leq a_{n+1} ;\)

(C) there is an integer k such that \(a_{n+k}=a_n\) for all n.

(D) None of the above.

I.S.I. Entrance B. stat. 2003, Objective, Problem 1

Sequence and series

6 out of 10

Secrets in mathematics.

Knowledge Graph

consecutive terms of a series- knowledge graph

Use some hints

we can put value of n , as it is equal to list of given natural numbers. n=1,2,3,4,......... and verify the result with the option.

We can see weather the series is converging or diverging to a value, means is there any pattern of the next term with the previous term in the sense of ratio of the two terms.

Also to generalize everything we can put n+1 in place of n in the expression \(a_n = \frac{{10^{n+1}+1}}{10^n +1}\) and then we can divide the \(a_{n+1}\) by \(a_{n}\) to get the required comparison ratio.

Related Program

Math Olympiad

I.S.I. & C.M.I. Entrance Program

Taught by students and alumni of I.S.I. & C.M.I.

Learn More

Subscribe to Cheenta at Youtube

Numbers on a blackboard

[et_pb_section fb_built="1" _builder_version="3.22.4"][et_pb_row _builder_version="3.22.4"][et_pb_column type="4_4" _builder_version="3.22.4"][et_pb_text _builder_version="3.22.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3" custom_padding="20px|20px|20px|20px"]

Understand the problem

[/et_pb_text][et_pb_text _builder_version="3.22.4" text_font="Raleway||||||||" background_color="#f4f4f4" box_shadow_style="preset2" custom_margin="10px||10px" custom_padding="10px|20px|10px|20px"]Azambuja writes a rational number $q$ on a blackboard. One operation is to delete $q$ and replace it by $q+1$; or by $q-1$; or by $\frac{q-1}{2q-1}$ if $q \neq \frac{1}{2}$. The final goal of Azambuja is to write the number $\frac{1}{2018}$ after performing a finite number of operations. Show that if the initial number written is $0$, then Azambuja cannot reach his goal.

[/et_pb_text][et_pb_text _builder_version="3.22.4" text_font="Raleway||||||||" background_color="#f4f4f4" box_shadow_style="preset2" custom_margin="10px||10px" custom_padding="10px|20px|10px|20px"][/et_pb_text][/et_pb_column][/et_pb_row][et_pb_row _builder_version="3.22.4"][et_pb_column type="4_4" _builder_version="3.22.4"][et_pb_accordion open_toggle_text_color="#0c71c3" _builder_version="3.23.3" toggle_font="||||||||" body_font="Raleway||||||||" text_orientation="center" custom_margin="10px||10px"][et_pb_accordion_item title="Source of the problem" open="on" _builder_version="3.23.3" title_text_shadow_horizontal_length="0em" title_text_shadow_vertical_length="0em" title_text_shadow_blur_strength="0em" closed_title_text_shadow_horizontal_length="0em" closed_title_text_shadow_vertical_length="0em" closed_title_text_shadow_blur_strength="0em"]Brazilian national mathematical olympiad 2018[/et_pb_accordion_item][et_pb_accordion_item title="Topic" open="off" _builder_version="3.23.3" title_text_shadow_horizontal_length="0em" title_text_shadow_vertical_length="0em" title_text_shadow_blur_strength="0em" closed_title_text_shadow_horizontal_length="0em" closed_title_text_shadow_vertical_length="0em" closed_title_text_shadow_blur_strength="0em"]Invariance[/et_pb_accordion_item][et_pb_accordion_item title="Difficulty Level" open="off" _builder_version="3.23.3" title_text_shadow_horizontal_length="0em" title_text_shadow_vertical_length="0em" title_text_shadow_blur_strength="0em" closed_title_text_shadow_horizontal_length="0em" closed_title_text_shadow_vertical_length="0em" closed_title_text_shadow_blur_strength="0em"]Easy[/et_pb_accordion_item][et_pb_accordion_item title="Suggested Book" open="off" _builder_version="3.23.3" title_text_shadow_horizontal_length="0em" title_text_shadow_vertical_length="0em" title_text_shadow_blur_strength="0em" closed_title_text_shadow_horizontal_length="0em" closed_title_text_shadow_vertical_length="0em" closed_title_text_shadow_blur_strength="0em"]Problem Solving Strategies by Arthur Engel[/et_pb_accordion_item][/et_pb_accordion][et_pb_text _builder_version="3.22.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3" custom_margin="48px||48px" custom_padding="20px|20px|20px|20px"]

Start with hints

[/et_pb_text][et_pb_tabs active_tab_background_color="#0c71c3" inactive_tab_background_color="#000000" _builder_version="3.23.3" tab_text_color="#ffffff" tab_font="||||||||" background_color="#ffffff"][et_pb_tab title="Hint 0" _builder_version="3.23.3"]

Do you really need a hint? Just try it yourself! [/et_pb_tab][et_pb_tab title="Hint 1" _builder_version="3.23.3"]It is always a good idea to try using the invariance principle in such problems. [/et_pb_tab][et_pb_tab title="Hint 2" _builder_version="3.23.3"]Make a change of variables to see patterns. [/et_pb_tab][et_pb_tab title="Hint 3" _builder_version="3.23.3"]Note that the operation is restricted to rational numbers. Hence, writing $latex q=\frac{r}{s}=(r,s)$ could help. [/et_pb_tab][et_pb_tab title="Hint 4" _builder_version="3.23.3"]Let us denote by $latex q_n$ the number on the board at the $latex n$th step. We shall use the new variable $latex a_n=2q_n-1$ (just to simplify the denominator). Clearly, $latex a_{n+1}$ is either $latex a_n\pm 2$ or $latex -\frac{1}{a_n}$. Writing $latex a_n=(r_n,s_n)$, this means that $latex (r_{n+1},s_{n+1})$ is either $latex (r_n \pm 2s_n,s_n)$ or $latex (-s_n,r_n)$. Thus, we need to find out if $latex (-1008,1009)$ is reachable starting from $latex (-1,1)$. However, (odd, odd) pairs can produce only other (odd,odd) pairs under this operation, and $latex (-1008,1009)$ is an (even, even) pair. Hence $latex \frac{1}{2018}$ cannot be reached starting from 0. [/et_pb_tab][/et_pb_tabs][et_pb_text _builder_version="3.22.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3" custom_margin="48px||48px" custom_padding="20px|20px|20px|20px"]

Watch the video (Coming Soon)

[/et_pb_text][et_pb_text _builder_version="3.22.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3" min_height="12px" custom_margin="50px||50px" custom_padding="20px|20px|20px|20px"]

Connected Program at Cheenta

[/et_pb_text][et_pb_blurb title="Math Olympiad Program" url="https://cheenta.com/matholympiad/" url_new_window="on" image="https://cheenta.com/wp-content/uploads/2018/03/matholympiad.png" _builder_version="3.23.3" header_font="||||||||" header_text_color="#e02b20" header_font_size="48px" link_option_url="https://cheenta.com/matholympiad/" link_option_url_new_window="on"]

Math Olympiad is the greatest and most challenging academic contest for school students. Brilliant school students from over 100 countries participate in it every year. Cheenta works with small groups of gifted students through an intense training program. It is a deeply personalized journey toward intellectual prowess and technical sophistication.[/et_pb_blurb][et_pb_button button_url="https://cheenta.com/matholympiad/" url_new_window="on" button_text="Learn More" button_alignment="center" _builder_version="3.23.3" custom_button="on" button_bg_color="#0c71c3" button_border_color="#0c71c3" button_border_radius="0px" button_font="Raleway||||||||" button_icon="%%3%%" button_text_shadow_style="preset1" box_shadow_style="preset1" box_shadow_color="#0c71c3" background_layout="dark"][/et_pb_button][et_pb_text _builder_version="3.22.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3" custom_margin="50px||50px" custom_padding="20px|20px|20px|20px"]

Similar Problems

[/et_pb_text][et_pb_post_slider include_categories="9" _builder_version="3.22.4"][/et_pb_post_slider][et_pb_divider _builder_version="3.22.4" background_color="#0c71c3"][/et_pb_divider][/et_pb_column][/et_pb_row][/et_pb_section]