We prove that the sequence of the characters of the Kirillov-Reshetikhin (KR) modules $W_{ m}^{ (a)}, m\in \mathbb{ Z}_{ m\geq 0}$ associated to a node $a$ of the Dynkin diagram of a complex simple Lie algebra $\mathfrak{ g}$ satisfies a linear recurrence relation except for some cases in types $E_7$ and $E_8$. To this end we use the $Q$-system and the existing lattice point summation formula for the decomposition of KR modules, known as domino removal rules when $\mathfrak{ g}$ is of classical type. As an application, we show how to reduce some unproven lattice point summation formulas in exceptional types to finite problems in linear algebra and also give a new proof of them in type $G_2$, which is the only completely proven case when KR modules have an irreducible summand with multiplicity greater than 1. We also apply the recurrence to prove that the function $\dim W_{ m}^{ (a)}$ is a quasipolynomial in $m$ and establish its properties. We conjecture that there exists a rational polytope such that its Ehrhart quasipolynomial in $m$ is $\dim W_{ m}^{ (a)}$ and the lattice points of its $m$-th dilate carry the same crystal structure as the crystal associated with $W_{ m}^{ (a)}$.
Categories: math.RT math.CO math.QA