Problem

Source: 2020 IGMO R2 #2 (C2) https://artofproblemsolving.com/community/c594864h2364137p19272184

Tags: combinatorics, composition



Given that $f(x) = x+1$ and $g(x) = 2x$, how many different ways are there of combining $f(x)$ and $g(x)$ (this means doing any number of compositions like $fg(x)$ or $g^3f^2g(x)$ etc) such that the resulting composition is $8x + 8m$ where $m \ge 0$ is an integer? Find a general formula for the number of possibilities in terms of $m$.