A proof of two congruences of P. Bala for the Motzkin numbers modulo p and p^2, with a generalization to coefficients of powers of a polynomial

We prove two congruences conjectured by P. Bala in the OEIS entry A001006 of the Motzkin numbers M(n) (February 10, 2022): M(n+p^k) == M(n) (mod p) for every prime p >= 3, k >= 1 and 0 <= n <= p^k - 3, and M(n+p^k) == M(n) (mod p^2) for every prime p >= 5, k >= 2 and 0 <= n <= p^(k-1) - 3. Both ranges are shown to be exactly sharp: M(2p^k-2) == M(p^k-2) - 1 (mod p) for every prime, and the congruence modulo p^2 fails at n = p^(k-1) - 2. The proof uses only the representation M(n) = [x^n] (1 - x^2)(1 + x + x^2)^n, the Frobenius congruence P(x)^(p^k) == P(x^(p^k)) (mod p) and a count of degrees; modulo p^2 it also uses the lemma [y^p](1 + y + y^2)^p == 1 (mod p^2) for p >= 5, which we derive from Babbage’s congruence binomial(2p-1, p-1) == 1 (mod p^2). The lemma fails for p = 3 (the coefficient is 7), which is exactly why Bala’s second statement requires p >= 5. Nothing in the argument is special to the Motzkin numbers: for every sequence a(n) = [x^(n+s)] Q(x) P(x)^(n+e) with integer polynomials P, Q we obtain a(n+p^k) == P_1 a(n) (mod p) and a(n+p^k) == c_p a(n) (mod p^2) in explicit ranges of n, where P_1 is the coefficient of x in P and c_p = [y^p] P(y)^p. For the sequences of the same family (central trinomial coefficients A002426, A005717, A005773) this gives the analogous congruences with their own ranges, which are new as far as we know. The two statements were left as “consistent” (true in all checked cases, no proof) by the author’s SyntheticMind engine in the batch of open statements of the core entries of the OEIS (October 5, 2026). On October 15 the engine was extended with a method for congruences with a free prime that computes exact p-adic valuations, generalizes the statement (exponent and family: the corollary for A002426, A005717 and A005773 came out of this step) and proves what it can with a written argument. The proofs use no computation; independent checks (Python 3, exact integers, with negative controls) and the engine’s output are distributed with the note, and the text was reviewed by an independent AI referee with its own programs. The use of AI is described in the paper. As of October 15, 2026 the statements were still marked as conjectures in the OEIS entry.