MathDB

recurrence relation wanted, number of numbers with n digits related

Source: Netherlands - Dutch NMO 1962 p3

January 31, 2023

number theoryrecurrence relationDigits

Problem Statement

Consider the positive integers written in the decimal system with

n

digits, the start of which is not zero and where there are no two sevens next to each other. The number of these numbers is called

u_n

. Derive a relation that expresses

u_{n+2}

in terms of

u_{n+1}

and

u_n