The other direction follows from the fact that the algorithm is bounded, and PA can simply show the execution trace of A in ≤CN steps.
Unimportant technical point: I think the length of the PA proof grows faster than this. (More precisely, the length in symbols, rather than the length in number of statements; we’re almost always interested in the former, since it determines how quickly a proof can be checked or be found by exhaustive search.) The obvious way of showing A()=1 in PA is to successively show for higher and higher t that “after t ticks, the Turing machine computing A() is in the following state, and its tapes have the following content”. But even to write out the contents of the tape of a Turing machine that has run for t ticks will in general take t symbols. So the obvious way of doing the proof takes at least O(t2) symbols. Moreover, I’m not sure whether we can get from “at time t, the configuration is such-and-such” to “at time t+1, the configuration is such-and-such” in a constant number of proof steps. I suspect we don’t need more than O(t3) symbols overall, but I’m not extremely confident. (I’d be quite surprised if the time turned out not to be polynomial, though!)
Unimportant technical point: I think the length of the PA proof grows faster than this. (More precisely, the length in symbols, rather than the length in number of statements; we’re almost always interested in the former, since it determines how quickly a proof can be checked or be found by exhaustive search.) The obvious way of showing A()=1 in PA is to successively show for higher and higher t that “after t ticks, the Turing machine computing A() is in the following state, and its tapes have the following content”. But even to write out the contents of the tape of a Turing machine that has run for t ticks will in general take t symbols. So the obvious way of doing the proof takes at least O(t2) symbols. Moreover, I’m not sure whether we can get from “at time t, the configuration is such-and-such” to “at time t+1, the configuration is such-and-such” in a constant number of proof steps. I suspect we don’t need more than O(t3) symbols overall, but I’m not extremely confident. (I’d be quite surprised if the time turned out not to be polynomial, though!)