Well Q_1 is just equal to 1*(2*1+1)/(2*1) = 3/2 Which is certainly less than 2*1+1.
Now Assume that the statement is true for n, i.e. Q_n < 2n+1
and consider Q_(n+1). Think how to (recursively) get
Q_(n+1) from Q_n. Well, Q_(n+1) = Q_n *
(2(n+1)+1)/2(n+1).
Since, by induction Q_n < 2n+1, we have that
Q_(n+1) < (2n+1) * [ (2n+3)/(2n+2) ]. Therefore we need to check
that (2n+1) * [ (2n+3)/(2n+2) ] <= (2(n+1) + 1)= 2n+3. Well just
multiply both sides by (2n+2) and, if necessary, expand:
(2n+1) * (2n+3) is the left hand side, while
(2n+2)*(2n+3)
the right hand side. Clearly the LHS is less than the right hands side.
We'll prove (approximately) that log(n) is big-O of Q_n as follows.
For each n , let H_n be the n-th Harmonic number, i.e. the sum of 1/k for k from 1 to n.
Now prove by induction that Q_n is bigger than (1/2) * H_n.
We know Q_1=3/2 and check that (1/2)H_1 = 1/2 * 1. So,
for the induction proof, assume that n >= 1 and that
Q_n> (1/2)H_n.
Again Q_(n+1) = Q_n * (2n+3)/(2n+2), while H_(n+1) = H_n +
(1/(n+1)).
So (1/2) H_(n+1) = (1/2) H_n + 1/2(n+1) which, by induction is
less than
Q_n + 1/2(n+1). Now look more closely at that expression for
Q_(n+1), and see that it equals
Q_n * (2n+2) + 1 ) / 2n+2 = Q_n * (1 + (1/(2n+2)) ) = Q_n + Q_n
/ (2n+2),
we are done so long as we know that Q_n is at least 1.
I guess that should have been part 1 of the question. You can easily prove this by induction, Q_1 is bigger than 1, and then each time we multiply it by a number bigger than 1. Alternatively we can notice that Q_n is equal to
(3/2)*(5/4) * ... * (2n+1/2n) -- i.e. a product of numbers each of which is bigger than 1.
Deduce that Q_n goes to infinity.
Then explain where your proof would break down if you tried to prove that S contained all integers greater than 20.
P(n) is the statement that n is in S and we want to prove P(n) for all n> 23.
Base step: 24 is in S (inspection)
Inductive: assume that n>23 and that P(k) is true for all k between 24 and n. We must prove that P(n+1) holds.
Well if P( (n+1) - 5) holds, then 5, (n+1)-5 are both in S and we can then say that (n+1) - 5 + 5 = (n+1) is in S. This is valid so long as k=(n+1) -5 is bigger than 23. I.e. this is valid so long as n+1< 29. In other words we have to check P(k) for k< 29 directly. Luckily we already did most of them above. We only missed 28, so 28 = 7+7+7+7 is in S.
10: a recursive algorithm for a^(2^n)
11. How does the number of multiplications used compare to the number used by power(a,0):= 1 and power(a,k+1):= a*power(a,k)?
Procedure pwr(a,n) if n=0 then pwr(a,0):=1 else begin k:=pwr(a,n-1) pwr(a,n):= k*k end
Number of multiplications in pwr(a,n) is about n+1, while the number in power(a,2^n) is of course about 2^n.