Try a few values, here's a table:
n 1 2 3 4 5 6 7 11n+17 28 39 50 61 72 83 94 2^n 2 4 8 16 32 64 128The pattern is clear, for 11n+17 we just keep adding 11, but once n is larger than 3, going from 2^n to 2^(n+1) adds much more than 11, but we have to wait till 2^n catches up.
Prove, by induction, that P(n): 11n+16 < 2^n for n>6.
Base step: n=7 has been verified above.
Induction: Assume n>6 and 11n+17 < 2^n. We must show that P(n+1) holds. Look at 11(n+1)+17 = 11n + 17 + 11, which by induction, is less than 2^n+11, and since n>6>4, it follows that 2^n+11<2^(n+1) which completes the proof.
We can prove by induction that S contains everything bigger than some N, if we can establish that each of N, N+1, N+2, N+3, and N+4 are in S . Because then to show that n+1 is in S we just argue, by induction, that (n+1)-5 is in S . This is easy. I don't think we get 31 in S. 32=27+5, 33=15+18, 34=25+9, 35, 36 are obvious.
We need some fact about gcd(a,b) in terms of smaller values. For example, gcd(a,b) = gcd(a-b,b). So here goes:
gcd(a,b) = a if a=b
and gcd(a,b) = gcd(a-b,b) if a>b, else
So u_3=3, u_4=4 (even though u_2+u_2 =4 but these are not distinct Ulam numbers), but 5 is not an Ulam number since 2+3 and 1+4 are both equal 5. u_5=6 (=u_2+u_4), 7 is out because 6+1 and 3+4. So far: 1,2,3,4,6 ; it looks like 9 is the next.
Prove by induction that there are infinitely many. It's better to do this by the well-ordering principle. Suppose that n is the smallest number such that there's no Ulam number bigger than n. So n=u_k for some k and we know that k> 2. Now clearly u_k + u_(k-1) is bigger than u_i+u_j for all other pairs j<=k and i< (k-1). Since we are assuming there are no other Ulam numbers, this would seem to imply that u_k+u_(k-1) is an Ulam number. ( Note that this does not prove that u_k+u_(k-1) is always an Ulam number. For example u_4+u_3 = 7 is not one).
Base case: n=1; plug n=1 into LHS, 1^3+(2+1)^3 = 28. Now the RHS, (2)^2 (2+4+1) = 4*7=28. So P(1) holds.
Assume that P(n) holds. Consider LHS of P(n+1) which is
1^3 + ... + (2n+1)^3 + ( 2(n+1) +1)^3.
By the induction hypothesis (P(n)) this is equal to (n+1)^2 * (2*n^2 + 4*n + 1) + ( 2*(n+1) +1)^3.
We don't need to be fancy, just carefully multiply and
2n^4+ 16n^3 + 47n^2 +60n+ 8
While the right hand side of P(n+1) is ( (n+1) +1)^2 * (2*(n+1)^2 + 4*(n+1) +1) which expands as
Well, what do you know (I used maple), the same thing. This completes the proof.
Check Base case n=5: 2^5=32. 5^2+5 = 30. So we are ok.
By induction: n> 4 and P(n) holds. We want to show 2^(n+1) > (n+1)^2 + (n+1). Well, 2^(n+1) = 2*2^n which, by induction, is greater than 2*(n^2+n). To finish the proof, we just have to prove that 2*(n^2+n) is greater than (n+1)^2 + (n+1). This isn't true for all n, but we only need it for n> 4. This is quite routine.
Here's the sequence 0 1 1 2 3 5 8 13 21 34 55 89 144
Well the pattern is clear: f_n is even iff n is a multiple of 3, i.e. if n == 0 (mod 3). It should even be clear why that's true (if you were the one who wrote down the sequence, it would have come to you).
Proof by induction: P(n) is the statement f_n is even iff n==0(mod 3)
P(0) or P(1) is clearly true.
Now assume that P(k) is true for all k at most n for some n>0. To prove P(n+1), there are three cases to check and once you realize that it is quite easy: n+1==0 (mod 3), n+1==1(mod 3), n+1==2(mod 3).
As is standard when a proof relies on more than just the previous case we have to check more than just the first case by hand. We did n=0, n=1 already, and we can see P(2), P(3) are also true. So now we can assume that n>= 3. Each case is similar. Suppose that n+1==0 (mod 3). Then f_(n+1) = f_n + f_(n-1). What about the congruence class of n and n-1? Well they are -1=2 and -2=1 respectively. Therefore, f_n and f_(n-1) are both odd, which of course means that f_(n+1) is even. Since n+1==0 (mod 3) this verifies P(n+1) for this case.
Case n+1==1(mod 3). In this case n==0(mod 3) and n-1==2(mod 3). Therefore f_n is even and f_(n-1) is odd. This means that f_(n+1) is odd which again verifies P(n+1) for this case.
The last case is similar.
Up above we developed a recursive algorithm for gcd(a,b) so let us see if that helps. Basically it was that
gcd(a,b) = gcd(a-b,b). So if we had gcd(a-b,b) = s' * (a-b) + t'
* b, then just multiply it out so that we have
gcd(a,b) = s' * a + (t'-s') * b.
Here goes then: Let us use S(a,b) to denote the coefficient of a and T(a,b) to denote the coefficient of b in the equation:
gcd(a,b) = S(a,b) * a + T(a,b) * b.
Base step: if a=b, then S(a,b)=a and T(a,b) = 0.
If a< b, then gcd(a,b) = gcd(b,a), so recursive call to
if a> b, then S(a,b) = S(a-b,a) and T(a,b) = T(a-b,b) - S(a-b,b).
Imagine that you have such a string, w , in front of you
are trying to see how it is constructed from a couple of shorter
strings of that form. That is how you get a recursive definition.
It's clear that if w has a 1 and a couple of 0's in the
first or last couple of spots then w is of the form
0w'10 or 1w'00, etc. So a generation rule like: if
w' is in S, then each of 100w', 10w'0, and a
few more like that will get all of this type. But what if
w starts and ends with a long string of 0's or starts and
ends with a long string of 1's. Then we expect that w is
obtained by sticking a couple of strings together. For example
how do you get 000111000 or 100101001? It looks like the only
reasonable way is:
0 001 1 100 0 and 1 001 0 100 1 .
Base: the empty string is in S. Generation: if w and w' are in S, then so are (I'm not sure if this is the shortest possible list):
001w rearranged in any order, i.e. 0 w 01, 1w00, ...
and w w', and 001ww' again arranged in any order.
It is easy to prove by induction that every member, w of S has the property that w(0) = 2*w(1).
Clearly every quite short string satisfying the property is in S. So let us assume, by induction, that w is a string such that w(0) = 2*w(1) and that every shorter string which has twice as many 0's as 1's is in S. We must prove that w is in S.
If w doesn't start and end with a 1, or start and end with two 0's then it is easy to see how to get it as some substring (3 shorter) in S with 2 0's and a 1 stuck at the right places beginning and end. Hence in those cases, w is in S. Therefore we assume w begins and ends with 2 0's. I'll leave the begin and ends with a 1 since it is similar.
Suppose that w has n elements for some n. For each integer
0<k< n, let wk denote the string consisting of the
first k elements of w. For each k, consider the quantity
2*wk(1) - wk(0)
. We are assuming that 2*wk(1) - wk(0) = 0 when k=n. Notice also that 2*wk(1) - wk(0) is 2 when k=n-2 and is equal to -2 when k=2. This quantity jumps up by 2 when the k-th member of w is a 1 and it drops by 1 when the k-th member of w is a 0. There is a smallest k (<n-2), where 2*wk(1) - wk(0) first becomes non-negative. If 2*wk(1) - wk(0) is equal to 0, then wk is in S and so is the tail of w with wk removed. On the other hand if 2*wk(1) - wk(0) is equal to 1, then set v to be the substring of w by going from position 2 to k-1 and let w' be the substring from position k+1 to n-1 and figure the argument that
w = 0 v 1 w' 0 is in S