Principle of Strong Induction Question?

Question

A pile starts with n sticks, with n>=2. The pile is split into two piles, and the product of the sizes of the piles is calculated. One of these new piles is then split into two piles, with the product of the sizes of these two new piles calculated and added to (the sum of) the previous product(s). This process continues until we have n piles with 1 stick in each.
For example, starting with 5 sticks, we could split 2, 3 (giving 6), then 2, 2, 1 (giving 6 + 2), then 1, 1, 2, 1 (giving 6 + 2 + 1), then 1, 1, 1, 1, 1 (giving 6 + 2 + 1 + 1 = 10).
Prove using strong induction that, no matter how the pile is split, the total at the end is always 1/2(n^2 -n).

Help?

Answer 1

First let's define f(n) to be the final sum of the products when we split a pile of n sticks. We wish to prove that f(n)=1/2(n^2-n). We will use strong induction to prove this. We assume that f(i)=1/2(i^2-i) for integers i such that 2<=i<=k for some integer k. We hope to prove that f(k+1)=1/2((k+1)^2-(k+1)). Let's first prove this works for the base case n=2. We can split a pile of 2 sticks in only 1 way (into 2 piles of 1 stick). Then the piles cannot be divided further and our product from the split is 1. We verify that 1/2(2^2-2) does indeed equal 1 and proceed.

Now let's consider a pile of n=k+1 sticks. Let's us split this pile into a pile of c sticks for integral c such that 1<=c<=k and a pile of (k+1)-c sticks. The product from this first split is

c(k+1-c).

Since both c and k+1-c (the sticks in the two piles) are always less than or equal to k, we can refer to our assumption to determine the sum of the products for each of these "subpiles." The two sums are given by f(c) and f(k+1-c) respectively. Thus the sum of the products when we split a pile of k+1 sticks is

c(k+1-c)+f(c)+f(k+1-c)
=c(k+1-c)+1/2(c^2-c)+
1/2((k+1-c)^2-(k+1-c)).

After you wade through the algebra (which I encourage you to try for practice) this expression becomes 1/2(k^2+k). The fact that the "c" disappeared shows that how you split the pile does not affect the resulting sum. Is this equal to the desired 1/2((k+1)^2-(k+1))? If you expand the latter you will find that it does indeed equal 1/2(k^2+k). Thus we have shown by strong induction that f(n)=1/2(n^2-n).

Answer 2

It all depends on what you are allowed to assume. If you are allowed to assume the usual principle of induction, then let L be the set of positive integers m such that ALL integers from 1 to m included are in K. Then obviously 1 ∈ L, and if n∈L, then clearly n+1∈L. So every positive integer is in L, hence also in K. For S, consider the set of integers for which S_n is true, and apply (1) to it.