Fork me on GitHub
Math for the people, by the people.

User login

high school mathematics

Type of Math Object: 
Topic
Major Section: 
Reference
Groups audience: 

Mathematics Subject Classification

00A20 no label found

Comments

Whats the units digit in the expansion of

(15+sqrt220)^19 + (15+sqrt220)^82

Form the recursion

a_{n+2} = 30 a_{n+1} - 5 a_n.

The solution of this recusrion with initial conditions

a_0 = 2

and

a_1 = 30

is

a_n = (15 + sqrt 220)^n + (15 - sqrt 220)^n.

Now, 15 - sqrt 220 = 0.1676..., so the latter
term will be much less than 0.1 when n = 19 or
n=84. Hence, (15+sqrt220)^19 will have the
same units digit as a_19 and (15+sqrt220)^82
will have the same units digit as a_84, so to
obtain your answer we simply add these units digits.

How are we to detemine these units digits?
Consider the recursion modulo 10 --- the units
digits of a_n are all zero when n > 0, so the
answer is 0.

Thanks rspuzio, but I am not so brilliant that I can understand all these things in one shot. Can you please all these in detail

Why did you form the recusrsion

a_{n+2} = 30 a_{n+1} - 5 a_n.

On what basis did you take the initial conditions

a_0 = 2 and a_1 = 30

and how did you get the solution

a_n = (15 + sqrt 220)^n + (15 - sqrt 220)^n.

Also can you please explain in detail how did you get the units
digits of a_n all zero when n > 0

Now I will go a bit slower and explain the motivation for what
I did. We want to look at (15 + sqrt 220)^19 and
(15 + sqrt 220)^84. Since 19 and 84 are big, it would take
a long time to simply compute the powers, so it would be nice
to have a short-cut.

Since 15 + sqrt 220 is irrational, it is not so easy to work with it;
it would be a lot nicer if one could work with rational numbers
instead.

Thinking of Binet's formula for Fibonacci numbers, my memory having
been jogged by the recently added entry on linear recurrences in the
right-hand column of the webpage, an idea for how to do this came
to me --- consider the quantity

a_n = (15 + sqrt 220)^n + (15 - sqrt 220)^n.

On the one hand, since this is the sum of a number with its conjugate,
it will be rational, in fact, it will be an integer. On the other
hand, since 15 - sqrt 220 = 0.1676..., the second term will be
quite negligibly small when n = 19 or n = 84, especially since we
are only interested in the first decimal place.

Following the analogy with the Fibonacci sequence suggests that the
way to compute this quantity is by means of a recursion, we only
need to figure out which recursion. To this end, write

(15 + sqrt 220)^n = p_n + q_n sqrt 220.

To find the recursion, multiply both sides by 15 + sqrt 220,
simplify, and equate coefficients:

p_{n+1} + q_{n+1} sqrt 220 =
(15 + sqrt 220)^{n+1} =
(15 + sqrt 220) (15 + sqrt 220)^n =
(15 + sqrt 220) (p_n + q_n sqrt 220) =
15 p_n + 15 q_n sqrt 220 + p_n sqrt 220 + 220 q_n =
(15 p_n + 220 q_n) + (p_n + 15 q_n) sqrt 220

Hence, we have

p_{n+1} = 15 p_n + 220 q_n

and

q_{n+1} = p_n + 15 q_n,

whence, by elimination, we may conclude

p_{n+2} = 15 p_{n+1} + 220 q_{n+1} =
15 p_{n+1} + 220 (p_n + 15 q_n) =
15 p_{n+1} + 220 p_n + 3300 q_n =
15 p_{n+1} + 220 p_n + 3300 (p_{n+1} - 15 p_n) / 220 =
30 p_{n+1} - p_n.

Now, if

(15 + sqrt 220)^n = p_n + q_n sqrt 220

then, taking the other sign of the square root,

(15 - sqrt 220)^n = p_n - q_n sqrt 220,

so a_n = 2 p_n, and hence a_n will satisfy the same
recursion, to wit

a_{n+2} = 30 a_{n+1} - 5 a_n

since it is linear. As for the initial values, we
simply substitute n=0 and n=0 into the definition to
find them:

a_0 = 2

a_1 = 30

we may now use our recursion to obtain a few more values:

a_2 = 890

a_3 = 26550

a_4 = 792050

a_5 = 23628750

Note that the units digit of all these values is zero. Furthermore,
if the units digit of both a_n and a_{n+1} is zero, it follows
from the recursion that the units digit of a_{n+2} will also be
zero. Hence, without need of further computation, we see that the
units digits of a_19 and a_84 will also both be zero.

Thanks rspuzio

Great work. You are really a genius. I really appreciate.

I am just confused with the ways to find divisibility by 11.
1) If sum of alternate digits is same then number is divisible by 11 -> this is sufficient but not necessary
2) If sum of digits is 11, then number is divisible by 11. This does not seem true always. For eg: 605 is divisible by 11 but 434 is not.

Can anyone please prove how to find divisibility by 11?

Sure. You add up the odd-position digits, and add up the even-position digits. If the two sums differ by a multiple of 11, then the number is divisible by 11.

This is easy to see by writing out the decimal representation. Without any carries, it's trivial; you have to think about it just a little bit to convince yourself that it works when you have to carry in the multiplication. But it's all straightforward.

November's challenge is dedicated to IBM Fellow Benoît Mandelbrot, who died on October 14, 2010, at the age of 85.

Let's define a function f on five variables (i, j, k, l, and m) as follows:

If (i-m)*(j-m) is zero then
f(i,j,k,l,m) ← ((abs(j-(1-k+l)*m)-m+1)* (abs(i-(k+l)*m)-m+1))
else
f(i,j,k,l,m) ← f(i mod m,
j mod m,
int(((i^j)&((m*l)^i))/m)^l^k^int(i/m),
int(((i^j)&((m*k)^i))/m)^l,
m/2)

Where
x^y means bitwise xor (exclusive or)
x&y means bitwise and (conjunction)
abs is the absolute value
mod is the modulo function
int means truncating downwards to an integer

What should be the input to the function f, and how do you need to interpret its output to associate it with Professor Mandelbrot?

Subscribe to Comments for "high school mathematics"