1) C_(k+1) = (2k+2)!/((k+2)!(k+1)!) = (2k+2)(2k+1)/(k+2)(k+1) * C_k
So, C_k divides C_(k+1) if that fraction is an integer. Simplifying it we have
2(2k+1) = m(k+2) => (4-m)k = 2(m-1) => k = 2(m-1)/(4-m)
Since k>=0, m<4 and m>=1 and we can simply test m=1,2,3. k is integer for all these 3 and we have k=0, k=1 and k=4. So, C_0 divides C_1, C_1 divides C_2 and C_4 divides C_5, no more cases like this occur.
2) C_k = (2k)!/k!(k+1)! = 1/k+1 (2k k) = (1 - k/(k+1)) (2k k) = (2k k) - (2k k+1)
The (n m) denotes the binomial "n choose m". We have to calculate C_k mod 2, so just apply
Lucas' theorem to the binomials. If we express k using binary digits, 2k is k shifted to the right with a 0 appended to the end.
From Lucas' theorem, (2k k) is even if, for some position d, the d-th digit on 2k is 0 and the d-th digit on k is 1, because (0 1) = 0 and all the others are 1. Now, assume k>0 and pick the least significant bit of k that's 1, the bit on the same position on 2k will be either 0, if k is the rightmost bit, or the bit to the right, which by our choice should be 0 too. This proves that (2k k) is even for k>0.
Now for (2k k+1). Also assume k>0 and pick the least significant bit of k that's 0, at position d. When you calculate k+1, this bit becomes 1, all others to the right become 0 and all others to the left don't change.
From our choice, the bit at position d on 2k is 1, and we get (1 1) = 1. To the right, k+1 has only 0 bits, so we get (x 0) = 1, so no problems there.
Now pick, if it exists, the rightmost bit of k that's 1 and is to the left of d, at position e. The bit on position e at 2k is necessarily 0, and since adding 1 to k doesn't change the bit at position e, we get (0 1) = 0 and (2k k+1) is even. If this bit doesn't exist then k is represented by a string of 1's, so for (2k k+1) we would have (1 1) in the leftmost bit, (0 0) in the rightmost and (1 0) for all others, and (2k k+1) is odd.
If k is represented by a string of 1's, then k = 2^j - 1, j>0. For this, we have (2k k) even and (2k k+1) odd, so the subtraction, C_k is odd. For all other k>0, both (2k k) and (2k k+1) are even, so C_k is even. It's trivial to check that C_0 is odd. Therefore, we conclude C_k is odd iff k = 2^j - 1, j>=0
EDIT: I solved the "if" part of 2) without using Lucas' theorem:
By counting the number of multiples of 2, 4, 8, 16, ... we get the number of factors of 2 in n!: sum(floor(n/2^k),k), k>=1
We use this to find how many factors of two are in (2n n) = (2n)!/(n!)²
So, there are sum(floor(2n/2^k),k) - 2*sum(floor(n/2^k),k) = sum(floor(2n/2^k)-2*floor(n/2^k),k) factors of two, if we let n/2^k = floor(n/2^k) + a_k and 2n/2^k = floor(2n/2^k) + b_k, we have:
floor(2n/2^k) - 2*floor(n/2^k) = 2a_k - b_k
a_k = (n mod 2^k)/2^k
b_k = (2n mod 2^k)/2^k
We have b_1 = 0 and b_k = a_(k-1). The k-th term of the sum is (n mod 2^k - n mod 2^(k-1))/2^(k-1). If n = 2^j - 1 then n mod 2^k = 2^k - 1, if k<=j, for k in that range the term reduces to (2^k - 2^(k-1))/2^(k-1) = 1, there are exactly j terms in that range. So the sum evaluates to j, meaning that, when n=2^j-1 there are exactly j factors of 2 in (2n n).
C_n = (2n n)/(n+1) = (2n n)/2^j, that means we take off all j factors of two, and an odd integer is left over.
I think I can prove the converse if I assume n + 1 = m*2^e, with m an odd integer, and prove that the number of factors of two in (2n n) is larger than e, maybe I'll do it later.
