Let g(n,k) be the number of partitions of n into exactly k parts, in which no part is a 1. Show that \(g(n,k) = g(n-2,k-1) + g(n-k,k).\)
Let f(n,k) be the number of partitions of n with k parts.
Consider a partition of n with k parts. By definition, there are g(n,k) is the number of partitions with n with k parts with no 1s. For a partition of n with k parts, we can add i 1s, to get a partition of n with k parts, so g(n,k) = f(n,k) + i.
Consider a partition of n with k - 1 parts. By definition, there are g(n,k - 1) is the number of partitions with n with k - 1 parts with no 1s. For a partition of n with k - 1 parts, we add (i - 1) 1s, to get a partition of n with k - 1 parts, so g(n,k) = f(n,k) + i - 1.
Consider a partition of n - k with k parts. By definition, there are g(n - k,k) is the number of partitions with n - k with k parts with no 1s. For a partition of n with k parts, we add i 1s, to get a partition of n - k with k parts, so g(n - k,k) = f(n,k) + i.
So the equation g(n,k) = g(n,k - 1) + g(n - k,k) becomes f(n,k) + i = f(n,k - 1) + (i - 1) + f(n - k,k) + i, or g(n,k) = g(n,k - 1) + g(n - k,k) + (i - 1).