MathDB
f (n, m) = f (n-1, m-1) + f (n-1, m-2) + f (n-2, m-1) + f (n-2, m-2) wanted

Source: OLCOMA Costa Rica National Olympiad, Final Round, 2018 Shortlist F2 (F= Functions)

October 1, 2021
functional equationfunctionalalgebraSequencecombinatorics

Problem Statement

Consider f(n,m)f (n, m) the number of finite sequences of 1 1's and 00's such that each sequence that starts at 00, has exactly n 00's and mm 1 1's, and there are not three consecutive 00's or three 1 1's. Show that if m,n>1m, n> 1, then f(n,m)=f(n−1,m−1)+f(n−1,m−2)+f(n−2,m−1)+f(n−2,m−2)f (n, m) = f (n-1, m-1) + f (n-1, m-2) + f (n-2, m-1) + f (n-2, m-2)
Back to ProblemsView on AoPS