Share
Explore BrainMass

Complete Induction Proof Help

I'm currently working on this problem and I know that P(1) = 0, P(2) = 1, P(3) = 3, P(4) = 6 so P(i+1) = P(i) + i but I'm kind of confused how to structure it...

Here is the complete question:

Consider a 1-player game using a bag of n marbles. The player starts by dividing the bag of marbles into two groups (so that each group contains at least 1 marble) of size k and n-k, and receives k(n-k) points for this move. The player continues the game by choosing a group at each step and dividing it into two groups (not necessarily of the same size) and receives the product of the sizes of the two new groups that he/she has made as points. These points are collected throughout the game. The game ends when there are no more groups that can be further divided (that is all remaining groups are of size 1). Prove (by complete induction) that no matter what strategy the player uses (for choosing the next group to break), he/she will always end up with n(n -1)=2 points at the end of the game.

Attachments

Solution Preview

For a proof by complete induction, we take n = 2 as a base case, and see that it can only be split in two groups of 1 and 1, so the final number of points we get is indeed 1*1 = 1 = n(n-1)/2 for n = 2.

Next, we assume that we have already proved the ...

Solution Summary

The solution assists with completing an induction proof.

$2.19