Linear recurrence relations are Delta_0-definable

We prove that the map sending A to A^n, where A is a k×k matrix with non-negative integer coefficients, is definable by a bounded arithmetic formula. As a consequence functions obtained by linear recurrence relations with non-negative integer coefficients are definable by bounded formulas. These include the Fibonacci sequence as well as functions of polynomial growth rate. It turns out that it is impossible to mimic the well known definition of the exponential map by bounded formulas. A combinatorial approach based on counting the number of solutions of linear diophantine equations is instead used.