In short
In short: a program is finished code that does one specific job - calculates, shows photos, sends messages. An app is a program made specifically for a phone or computer, with buttons you see and touch with your finger. Software is the umbrella word for all this invisible work behind the screen. Different names for the same thing, seen up close or from a distance.
Your phone by itself is an empty toolbox. It does nothing until you put tools in it. Instagram is a tool - it shows photos. The calculator is a tool - it calculates. Every tool inside was written by someone, to do exactly one task instead of you.
That task, hidden inside the tool, is called a program. It's a sequence of commands, written in advance, that the machine follows the same way every time. Press the calculator's button, and it doesn't think - it just runs the program built into it long ago.
The app is the program dressed in a screen you look at, and buttons you touch. That outfit makes it comfortable for you. Underneath, it's still the same program - code doing the work.
Software is the umbrella over everything listed. Say "install software" or "update the app", and you're talking about the same thing - putting a new tool in the box or improving an old one, so it does its job better.
Every app on your phone is a tool someone made to do exactly one job instead of you - nothing more, nothing less.
Here's where I trip up
As a designer the difference for me has always been this - the program is the tool itself, the app is the handle that fits your hand. When I make an interface, I fix the handle: I make it comfortable, clear, beautiful. The code underneath does the work, but you never see it, if I've done my part right.
So when you hear "update the software", don't panic. They're just swapping a tool in the box for a newer one, or touching up the handle to make it more comfortable for you.
Primary sources
Apple: App Store - how apps are reviewed (official)The visual is generated code-art, no third-party images.