Could probably be done using mathematical induction.
-
Show that it works for some initial value n=0
4^0 + 15*0 - 1 = 1 + 0 - 1 = 0 (a multiple of 9 *0)
Or for n=1, if you prefer
4^1 + 15*1 - 1 = 4 + 15 - 1 = 18 (a multiple of 9 *2)
Assume that the relationship is true for some arbitrary k, test that it is true for k+1
4^(k+1) + 15(k+1) - 1 =
4*4^k + 15k + 15 - 1 =
3*4^k + 4^k + 15k + 15 - 1 =
3*4^k + 15 + (4^k + 15k - 1) =
3*4^k - 3 + 18 + (4^k + 15k - 1) =
3*(4^k - 1) + 18 + (4^k + 15k - 1)
We know, by hypothesis, that it is true for value k alone. Then the right most term (4^k + 15k - 1) takes the proper form and is a multiple of 9 unto itself. The 18 is also a multiple of 9. We can ignore both of these terms.
3*(4^k - 1)
We need to test that this is also a multiple of 9. Or, due to the factor of 3, we need only test that (4^k - 1) is a multiple of 3.
If we can show that (4^k-1) is a multiple of 3 then we have succeeded in proving that 4^n + 15n - 1 is a multiple of 9
Proving that (4^k-1) is a multiple of 3 can also be done inductively. It is true.
We shall prove it though, just to be safe.
Test for n=0 or n=1
4^0 - 1 = 1 - 1 = 0, a multiple of 3
4^1 - 1 = 4 - 1 = 3, a multiple of 3.
Assume it is true for some k, 4^k-1. Test that it is true for k+1.
4^(k+1) - 1 =
4*4^k - 1 =
3*4^k + 4^k - 1 =
3*4^k + (4^k - 1)
The rigth most term (4^k -1) was assumed a multiple of 3 by hypothesis. The left most term is obviously a multiple of 3.
Thus, 4^k - 1 is a multiple of 3.
3*(4^k - 1) is also a multiple of 9.
And in turn 4^n + 15n - 1 is a multiple of 9.
4^0 + 15*0 - 1 = 1 + 0 - 1 = 0 (a multiple of 9 *0)
Or for n=1, if you prefer
4^1 + 15*1 - 1 = 4 + 15 - 1 = 18 (a multiple of 9 *2)
Assume that the relationship is true for some arbitrary k, test that it is true for k+1
4^(k+1) + 15(k+1) - 1 =
4*4^k + 15k + 15 - 1 =
3*4^k + 4^k + 15k + 15 - 1 =
3*4^k + 15 + (4^k + 15k - 1) =
3*4^k - 3 + 18 + (4^k + 15k - 1) =
3*(4^k - 1) + 18 + (4^k + 15k - 1)
We know, by hypothesis, that it is true for value k alone. Then the right most term (4^k + 15k - 1) takes the proper form and is a multiple of 9 unto itself. The 18 is also a multiple of 9. We can ignore both of these terms.
3*(4^k - 1)
We need to test that this is also a multiple of 9. Or, due to the factor of 3, we need only test that (4^k - 1) is a multiple of 3.
If we can show that (4^k-1) is a multiple of 3 then we have succeeded in proving that 4^n + 15n - 1 is a multiple of 9
Proving that (4^k-1) is a multiple of 3 can also be done inductively. It is true.
We shall prove it though, just to be safe.
Test for n=0 or n=1
4^0 - 1 = 1 - 1 = 0, a multiple of 3
4^1 - 1 = 4 - 1 = 3, a multiple of 3.
Assume it is true for some k, 4^k-1. Test that it is true for k+1.
4^(k+1) - 1 =
4*4^k - 1 =
3*4^k + 4^k - 1 =
3*4^k + (4^k - 1)
The rigth most term (4^k -1) was assumed a multiple of 3 by hypothesis. The left most term is obviously a multiple of 3.
Thus, 4^k - 1 is a multiple of 3.
3*(4^k - 1) is also a multiple of 9.
And in turn 4^n + 15n - 1 is a multiple of 9.