Seductive Recursive Sequences

Algebra Level 2

( α n ) (\alpha_n) and ( β n ) (\beta_n) are two sequences defined recursively as α n = 2 α n 1 + 1 \alpha_n=2 \alpha_{n-1}+1 and β n = 8 β n 1 + 1 \beta_n=8 \beta_{n-1}+1 with α 0 = β 0 = 0. \alpha_0=\beta_0=0. Find the ratio

α 2016 β 672 . \frac{\alpha_{2016}}{\beta_{672}}.


The answer is 7.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

4 solutions

Lê Triết
Apr 16, 2015

How did you replace 2(a_ n-1 + 1) with 2^n(a_0+1)?

Kevin Li - 6 years, 1 month ago
Nicholas Stearns
Apr 17, 2015

It's easy to show using number base expansion that, in general, for a recursively defined sequence a n = x a n 1 + 1 a_n=xa_{n-1}+1 , a n = x n 1 x 1 a_n=\frac{x^n-1}{x-1} . In this case, α n = 2 n 1 \alpha_n=2^n-1 and β n = 8 n 1 7 \beta_n=\frac{8^n-1}{7} . Because 2016 672 = 3 \frac{2016}{672} = 3 , the fraction becomes α 3 n β n = 2 3 n 1 8 n 1 7 = 7 8 n 1 8 n 1 = 7 \frac{\alpha_{3n}}{\beta_n}=\frac{2^{3n}-1}{\frac{8^n-1}{7}}=7\frac{8^n-1}{8^n-1}=7 .

Kevin Li
May 6, 2015

Literally my first post, so go easy on me. I'm also not much of a trained mathematician, but I've experience in doing contest questions.

Rocco Dalto
Feb 1, 2017

α N = k = 0 N 1 2 k = 2 N 1 \alpha_{N} = \sum_{k = 0}^{N - 1} 2^{k} = 2^{N} - 1

β J = k = 0 J 1 8 k = 8 J 1 = 2 3 J 1 \beta_{J} = \sum_{k = 0}^{J - 1} 8^{k} = 8^{J} - 1 = 2^{3 * J} - 1

α N β J = 7 ( 2 N 1 ) 2 3 J 1 \implies \frac{\alpha_{N}}{\beta{J}} = \frac{7 * (2^{N} - 1)}{2^{3 * J} - 1}

For N = 2016 N = 2016 and J = 672 3 J = 2016 J = 672 \implies 3 * J = 2016 \implies

α 2016 β 672 = 7 \frac{\alpha_{2016}}{\beta_{672}} = \boxed{7} .

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...