Proving Heap's Algorithm for Generating Permutations

I need to prove the correctness of Heap's algorithm for generating permutations. The pseudocode for it is as follows:

HeapPermute(n)
//Implements Heap’s algorithm for generating permutations
//Input: A positive integer n and a global array A[1..n]
//Output: All permutations of elements of A
if n = 1
   write A
else
   for i ←1 to n do
   HeapPermute(n − 1)
   if n is odd
      swap A[1] and A[n]
   else swap A[i] and A[n]

(taken from Introduction to the Design and Analysis of Algorithms by Levitin)

I know I need to use induction to prove its correctness, but I'm not sure exactly how to go about doing so. I've proved mathematical equations but never algorithms.

I was thinking the proof would look something like this...

1) For n = 1, heapPermute is obviously correct. {1} is printed. 
2) Assume heapPermute() outputs a set of n! permutations for a given n. Then 
??

I'm just not sure how to go about finishing the induction step. Am I even on the right track here? Any help would be greatly appreciated.

1. For n = 1, heapPermute is obviously correct. {1} is printed.
2. Assume heapPermute() outputs a set of n! permutations for a given n. Then
3. ??

Now, given the first two assumptions, show that heapPermutate(n+1) returns all the (n+1)! permutations.