Independent Sets of Cycles proof Involves Combinations

[rbzima]

Homework Statement

Let $$C_n$$ Recalling our notation from class, we know that $$I_0(C_n) = 1$$ and $$I_1(C_n) = n.$$ Prove that for $$k > 1,$$

$$I_k(C_n)=\left(\frac{n}{k}\right)\left(\stackrel{n-k-1}{k-1}\right)$$

Homework Equations

$$I_k$$ implies number of independent sets of size k
$$C_n$$ implies the cycle with n vertices.
Therefore, $$I_k(C_n)$$ implies the number of independent sets of size k in some cycle with n vertices.
$$I_k\left(C_n\right)=I_k\left(C_{n-1}\right)+I_{k-1}\left(C_{n-2}\right)$$

The Attempt at a Solution

I've worked through the algebra to a point where it becomes rather disheartening, and it seems to be getting no where whatsoever. I've tried thinking of a combinatorial proof for this, however cannot come up with any scenario to think of or how it might be applied in this instance. If anyone can simply lead me in the right direction, that would be totally fantastic!

 

[kurt.physics]

Base Case: k = 2I_2(C_n) = \left(\frac{n}{2}\right)\left(\stackrel{n-2-1}{2-1}\right)I_2(C_n) = \left(\frac{n}{2}\right)\left(\stackrel{n-3}{1}\right)I_2(C_n) = \frac{n(n-3)}{2}Inductive Hypothesis: Assume for some k>1, I_k(C_n)=\left(\frac{n}{k}\right)\left(\stackrel{n-k-1}{k-1}\right)Inductive Step: Show that for k+1, I_{k+1}(C_n)=\left(\frac{n}{k+1}\right)\left(\stackrel{n-k-2}{k}\right)I_{k+1}(C_n)=I_{k+1}(C_{n-1})+I_k(C_{n-2})=\left(\frac{n-1}{k+1}\right)\left(\stackrel{n-1-k-2}{k}\right)+\left(\frac{n-2}{k}\right)\left(\stackrel{n-2-k-1}{k-1}\right)=\frac{(n-1)(n-k-2)}{k+1}+\frac{(n-2)(n-k-1)}{k}=\frac{n(n-k-2)+(n-1)(n-k-1)}{k+1}=\frac{n(n-k-1)}{k+1}Therefore, I_{k+1}(C_n)=\left(\frac{n}{k+1}\right)\left(\stackrel{n-k-2}{k}\right)By the Principle of Mathematical Induction, we can conclude that for all k>1, I_k(C_n)=\left(\frac{n}{k}\right)\left(\stackrel{n-k-1}{k-1}\right)