Should I use rudder to recover from power-on stalls?
Your instructor is correct.
I've never seen a C172 where the POH actually discusses stall recovery besides saying it's 'standard'. I was taught to keep the airplane in balance using rudder in the approach to the stall, and manage any wing drops with rudder in a fully developed power off stall (I'm in the UK, not sure how the US is different). However, that isn't the procedure for a power on stall. The FAA Airplane Handling Handbook section 4-8 on power on stalls states:

The pilot must promptly recognize when the stall has occurred and take
action to prevent a prolonged stalled condition. The pilot should
recover from the stall by immediately reducing the AOA and applying as
much nose-down control input as required to eliminate the stall
warning, level the wings with ailerons, coordinate with rudder, and
smoothly advance the power as needed. Since the throttle is already at
the climb power  setting,  this  step  may  simply  mean  confirming
the  proper power setting.

In a power on stall if you get a big wing drop the rudder is not going to lift the wing, and coarse rudder movements could stress the airplane, see the AA 587 crash. So balance with rudder, but most importantly reduce your angle of attack with as much forward stick as you need.