Discrete structures

I have provided to question and solution please just inform me weather this is the correct solution thanks !!

Problem 2) (3 points): Prove that every amount of postage n 2 12 cents can be made from 4Cent and 5Cent stamps. (Hint: You might need to prove the statement separately for n = 12,13,14,15 before attempting an induction proof. Note that this recurrence relation is not homogeneous, since the second term (6^(n-1)) is not a multiple of a(n-1). Explanation: Step 1: To find the recurrence relation for an, let's consider the last digit of an n-digit codeword. Case 1: The last digit is less than 7. In this case, the number of valid n-digit codewords is the same as the number of valid (n-1)-digit codewords, since the number of digits greater than or equal to 7 remains the same. Case 2: The last digit is 7. In this case, the number of valid n-digit codewords is the number of invalid (n-1)-digit codewords, since adding a 7 to an invalid codeword makes it valid, and adding a digit less than 7 to a valid codeword keeps it valid. Case 3: The last digit is greater than 7. In this case, the number of valid n-digit codewords is the same as the number of valid (n-1)-digit codewords, since adding a digit greater than 7 to a valid codeword does not change the parity of the number of digits greater than or equal to 7. Therefore, we can write the recurrence relation for an as follows: an = a(n-1) + bn-1 - a(n-2) where bn-1 is the number of (n-1)-digit codewords that do not contain a digit greater than or equal to 7, and the last term subtracts out the invalid (n-2)- digit codewords that become valid by adding a 7 as the last digit. To find bn-1, we can use the fact that the number of (n-1)-digit codewords that do not contain a digit greater than or equal to 7 is simply 6^(n-1), since each digit can be any of the 6 values less than 7. Therefore, we have: an = a(n-1) + 6^(n-1) - a(n-2) This is the recurrence relation for an