MathDB
2^k divides a_n = 2*a_(n-1) + a_(n-2)

Source: IMO ShortList 1988, Problem 1, Bulgaria 1, Problem 1 of ILL

September 13, 2008
modular arithmeticlinear algebraalgebraSequenceDivisibilityLinear RecurrencesIMO Shortlist

Problem Statement

An integer sequence is defined by { a_n = 2 a_{n-1} + a_{n-2}},   (n > 1),   a_0 = 0, a_1 = 1. Prove that 2k2^k divides ana_n if and only if 2k2^k divides nn.
Back to ProblemsView on AoPS