Hint : use Generalized De Morgan Laws for logic (Theorem 1.3.12 page 21),
Actually 67 and 70 are equivalent.
Hint : 1(1!) + 2(2!) + 3(3!) + ... + n(n!) + (n+1) (n+1)!
= (n+1)! - 1 + (n+1)(n+1)! = ????
Proof by Induction :
Basic step : for n = 24, 25 , 26, 27 (we explicitly show how these can be achieved)
24 = 2 ´ 5 + 2 ´ 7
25 = 5 ´ 5
26 = 1 ´ 5 + 3 ´ 7
27 = 4 ´ 5 + 1 ´ 7
Inductive step : (strong form is required)
Let's assume that the statement holds for all k such that n ³ k ³ 24.
Then for n + 1 cents postage case,
if (n + 1) - 5 = n - 4 ³ 24 , then by inductive assumption,
(n-4) cents can be achieved by using only 5-cents and 7-cents stamps, and
hence (n+1) cents can be achieved by using one extra 5-cent stamp as
in (n-4) cents case.
if (n-4) < 24 then n must be one of those values : 24 , 25, 25 or 27
(since n ³ 24 ), and it has been justified in basic step.
Hence the statement is true for all n ³ 24.
Can you prove the similar statement ?
Show that postage of 24 cents or more can be achieved by using only 5-cent and 8-cent stamps.
Proof :
Basic step : ( n = 1 case) 7 1 - 1 = 7 - 1 = 6 and is divisible by 6.
Inductive step : Assuming the statement is true for case n , i.e.
7 n -1 is divisible by 6
then for case n+1 :
7 n+1 - 1 = 7 * 7 n - 1 = 7 * (7 n -1 ) + 6
is also divisible by 6 since both terms are divisible by 6.
The inductive step is complete.
Proof :
Basic step : (n = 1 case) 31 + 7 1 - 2 = 3 + 7 - 2 = 8 is divisible by 8.
Inductive Step: Assuming that 3n + 7 n - 2 is divisible by 8,
For case n + 1 :
3n+1 + 7 n+1 - 2 = 3 * 3n + 7 * 7 n - 2
= 7 * (3n + 7 n - 2 ) - 4 * 3n + 12
= 7 * (3n + 7 n - 2 ) - 12 * (3n-1 - 1)
Since 3n - 1 - 1 is always even for n = 1,2,3 ...... (**why?)
** if you are not quite sure, you can prove it by induction!
so 12 * (3n-1 - 1) is a multiple of 24 and is divisible by 8
and hence 3n+1 + 7 n+1 - 2 is divisible by 8 since
both 7 * (3n + 7 n - 2 ) and 12 * (3n-1 - 1) are divisible by 8.
Hint : 11n+1 - 6 = 11* 11n - 6 = (5 + 6)11n - 6
= 5 *11n + 6 * 11n - 6 - 6
= 5 * 11n + 6 * (11n - 6 ) + 36 - 6
= 5 * 11n + 6 * (11n - 6 ) + 30
Hint : 6 * 7 n+1 - 2 * 3 n+1
= 7 * 6 * 7 n - 3 * 2 * 3 n
= 7 * ( 6 * 7 n+1 - 2 * 3 n+1 ) + 7 * 2 * 3n - 3 * 2 * 3n
= 7 * ( 6 * 7 n+1 - 2 * 3 n+1 ) + 8 * 3n