In this case P(n) is of course the statement that SUM(2(-7)^k :
k=0..n) is equal to [1 - (-7)^(n+1)]/4.
Substitute n=0 to see if P(0) is true: SUM(2(-7)^k :k= 0..0) is equal to 2(-7)^0 = 2. While [1 - (-7)^1] /4 = 2. So it, i.e. P(n), is true for n=0.
Now assume n is greater or equal 0, and that P(j) is true for all
0<= j < n+1.
SUM up to n+1 is equal to SUM up to n plus the (n+1)-st term so
SUM( 2 (-7)^k : k=0... n+1) = [1-(-7)^(n+1)/4 + 2 (-7)^(n+1) by
the inductive assumption. [1-(-7)^(n+1)/4 + 2 (-7)^(n+1) =
[1 - (-7)^(n+1) + 8 (-7)^(n+1)] / 8 = [ 1 + 7 * (-7)^(n+1)] / 4 =
[1 - (-7) * (-7)^(n+1) ] / 4 .
Let P(n) be the statement that SUM( 1/k(k+1) : k=1..n) = n/(n+1).
We've already checked n=1, n=2, .., n=4.
By induction assume that n>3 and that P(j) is true for all j<n+1. We wish to now verify that P(n+1) holds.
Clearly SUM( 1/k(k+1) : k=1.. n+1) = SUM( 1/k(k+1) : k=1.. n) +
1/(n+1)(n+2). By inductive assumption P(n) we have that this sum
is then equal to n/(n+1) + 1/(n+1)(n+2). Put these over the common
denominator to get
[n(n + 2)+1]/(n+1)(n+2) = [ n^2 + 2n + 1 ] / (n+1)(n+2) = n+1 /
n+2
Trying values we find that if n=6, then 3^6 = (27)^2 = 729 and 6!=720, OK not yet but then n=7 gives 3^7 = 3*729 = 3*720 + 3*9 and 7! = 7 * 720 = 3*720 + 4*720, clearly much bigger.
Now assume that n> 6 and that 3^j < j! for all 6 < j < n+1. This is easy now: 3^n < n! by inductive assumption, hence 3*3^n < 3 * n! which in turn is less than (n+1) * n! since 6< (n+1).
To do this by induction, check that 1^3+2*1 = 3 is divisible by 3. Assume that for some integer n> 0, n^3+2n is divisible by 3. Look at (n+1)^3 + 2(n+1) and try to see if the previous term, n^3+2n can help. (n+1)^3 = n^3 + 3n^2 + 3n + 1 (the binomial coefficients). Hence (n+1)^3+2(n+1) = n^3 + 2n + [3n^2 + 3n + 1 + 2]. By inductive assumption n^3+2n is divisible by 3 and by inspection, 3n^2 + 3n + (1+2) is divisible by 3.
Well we just play around with this (i.e. replacing f_m by f_(m-1) + f_(m-2)) whenever you want to see if you can get somewhere with it. It took me a little while before I thought of replacing just one of those f_(n+1)'s. I knew we didn't want f_(n+2) in there.
f_(n+2) * f_n - f_(n+1)^2 =
( f_(n+1) + f_n ) * f_n - f_(n+1) * ( f_n + f_(n-1) ) =
cancel terms = f_n^2 - f_(n+1) * f_(n-1) = - [f_(n+1) f_(n-1) -
f_n^2 ] = - (-1)^n by induction hypothesis.
Procedure RecMax([a_1,..., a_n] : list) x := RecMax([a_1, ..., a_{floor(n/2)}]) y := RecMax([a_{floor(n/2) +1}, ..., a_n]) if x< y then output y else output xIf we let f(n) denote the number of steps needed to find the maximum of a list with n elements, then for n an even number, we have the recurrence relation: f(n) = 2 f(n/2) + 1
In this case, from our book formula f(n) = a f(n/b) + C, we have that a=2 and b=2, hence our algorithm is O(n^{log(2)})= n.
I suppose it's clear we can't get O(log(n)) steps since we have to at least READ every element of the list.
Prove by induction: P(n) is the assertion that f(n) = n^2. Clearly P(1) is true. Assume that n is some positive integer and that P(n) is true. f(n+1) = f(n) + (2(n+1)-1) = (by induction) = n^2 + 2(n+1) - 1 = n^2 + 2n + 1 = (n+1)^2.
Now try Section A3 for more practice. To reduce confusion, let a_n denote f_n. We can set a_0 = 0 and still have that a_1 = a_0 + 2(1) - 1, hence our recursion holds for all n> 0.
Let the generating function for {a_n} be denoted by g(x) and do
the usual thing:
g(x) = 0 + SUM( a_n x^n : n=1...) = SUM ( (a_(n-1) + 2n-1) x^n :
n = 1 ...)
g(x) = x g(x) + 2 * SUM( n x^n : n=1...) - x * SUM(x^n : n=0...)
= x g(x) + 2x * SUM( n x^(n-1) : n=1...) - x/(1-x)
At this point we have to notice/recall that SUM(n x^(n-1) : n=1...) is just the derivative of SUM( x^n : n=0...), hence it is equal to 1/(1-x)^2. So
g(x) = x g(x) + 2x * 1/(1-x)^2 - x/(1-x). Now solve for g(x).
g(x) * (1-x) = [2x -(1-x)*x]/(1-x)^2, then g(x) =
[x^2 + x]/(1-x)^3.
Well we didn't do any like this (but on the other hand we know the answer already): g(x)= [x^2 +x ] /(1-x)^3 = 2x^2/(1-x)^3 + (x-x^2)/(1-x)^3 = 2x^2 / (1-x)^3 + x/(1-x)^2.
We broke it up like this because 2/(1-x)^3 is the
derivative of 1/(1-x)^2 and so is the second derivative of
1/(1-x). Similary 1/(1-x)^2 is the derivative of 1/(1-x). Thus we
have that g(x) = x^2 * d^2[ 1/(1-x) ]/dx^2 + x * d[1/(1-x)]/dx.
Then g(x) = x^2 * SUM( n(n-1) x^(n-2) : n=2...) + x * SUM( n
x^(n-1) : n=1...) =
= SUM ( n(n-1) x^n : n=2...) + SUM( n x^n : n=1...) = SUM (
[n^2-n+n] x^n : n=1...) ( a little fiddling with n=1) = SUM( n^2
x^n : n=1...) as required.
I hope it's enough. Exercise 1: prove by induction that every string in S has twice as many 1's as 0's. I.e. true for base, assume it is so for x, y in S, then it is so for the new ones added by the generation rule.
Exercise 2: Prove that if z is any string with twice as many 1's as 0's then z is in S. We cannot induct on the generation rule for S since we are supposed to let z be any string at all; by only talking about the rules for S then we may not be considering all possible z. The best attack is to say P(n): every string z of length n with twice as many 1's as 0's will be in S. Prove P(0), P(1), P(2) by inspection (we do the first 3 because we anticipate that we will be subtracting 3 from the length of z).
Now suppose that n+1 is an integer > 2 and that P(j) is true for all j such that 0<= j < n+1. I.e. if y is any string of length at most n which has twice as many 1's as a 0's, then y is in S. Let z be any string of length n+1 which has twice as many 1's as 0's. We have to examine cases (how z starts or ends) to see which generation rule for S will be of help.
43 lambda, 0x, x1 for x in S so what's S?
Try constructing S for a while to get the pattern. S_0 = {lambda,0,1}. S_1 = {lambda, 0, 1, 00, 01, 01, 11} repetitions since I just took x through S_0 and applied rules for each x. S_2 = { lambda, 0, 1, 00, 01, 11, 000, 001, 011, 001, 011, 111} = {lambda, 0,1, 00, 01, 11, 000, 001, 011, 111}
Ready to guess? S is all strings of the form 00...0011...1 (where there can be no 0's and no 1's). I.e. no 0 is to the right of any 1.
Prove it by induction: First every string in S has this form: if x has the form then certainly 0x and x1 do as well.
Conversely P(n): if s is a string of length n in which no 0 is to the right of a 1, then s is in S. P(0) and P(1) are clear.
Assume P(n) and prove P(n+1). Let s be a string. If all 1's then s = x1 for a string x with one fewer 1. By inductive assumption, x is in S, hence by S-rule, x1 is in S. If s has a 0, then the left most character of s is a 0. Therefore s has the form 0x and by inductive assumption x is in S (again it is shorter and certainly doesn't have a 0 to the right of a 1).
44 abc bac acb and abcx abxc xabc axbc are in S, show that every member of S has length divisible by 3.
Easy induction. I'm thinking a great question is to prove that for every every integer j, there is an s in S such that s has j consecutive a's in it.
d+1 consecutive numbers means some b, b+1, ..., b+d. Send each to its remainder mod d means is a function (pigeons to holes) which sends d+1 numbers to d possible values (some r between 0 and d-1). Therefore two are sent to the same value. (Consecutive didn't matter)
8 5 integer pairs in plane gives two such that midpoint of line segment is integer.
Let (xi, yi) for i=1...5 denote the 5 integer pair points in the
plane. What is the formula for the midpoint of the line segment
joining (xi, yi) to (xj, yj). Well the slope is m = (yj - yi) /
(xj - xi). Half way along the x-axis from these two points takes
you to xi + (xj - xi)/2 = (xi + xj) /2. Take that value for x and
plug into the equation for the line which is y - yi = m ( x - xi).
OK, so y - yi = m ( (xi+xj)/2 - xi) = m (xj - xi)/2 and since m
has a denominator equal to xj - xi we get
y- yi = (yj-yi) /2 so y = (yi+yj)/2 (i.e. the midpoint (centre
of mass) is just
the average of the x-coords and the average of the y-coords).
Summarizing the above analysis (pigeon hole almost always involves
some analysis of the problem before applying the Principle).
The midpoint between point i and point j is M(i,j) = ( (xi+xj)/2 ,
(yi+yj)/2 ). This is a pair of integers if we can divide by two
which simply means xi and xj should both be even or both be odd
and similarly for the y values. Construct 4 pots to send the
values of i=1...5.