Let there be a set containing the following digits: {1,2,3,4,5,6,7,8,9}.
If I choose 5 digit blocks, where the digits are arrange in consecutive ascending order, then the following blocks are possible:
1) 12345
2) 23456
3) 34567
4) 45678
5) 56789
I can intuitively see the pattern, and come up with the following expression to get the number of blocks in a set of digits (where n is number of digits in the set, and k is the number of digits in a block): (n+1)-k.
How can I prove this general equation to be true for all sets and blocks, regardless of their size? In other words, how do I derive this expression analytically rather than intuitively?
Best Answer
To prove it analytically, you just spell out what you've already observed. E.g. you could introduce another symbol where $p$ is the position of the first element of the block, counting from position 1 to position $n$. You could call $l$ the position of the last element in the block.
Since the block has $k$ elements, $l = p + k -1$.
Since the right hand end of the block has to be contained in the set, $l \le n \Rightarrow p \le n + 1 - k$.
But also $p \ge 1$ since the left hand end of the block has to be contained in the set as well.
Apart from those two constraints, $p$ can be anything. So $p$ can be $1, 2, ... n + 1 -k$.
Since $p$ refers to the first element of the block, and the first block starts at position $1$, $p$ can serve as a counter for the number of blocks in the set; the last block in the set has $p = n + 1 - k$ and corresponds to the total number of blocks in the set.