for n>=0, let \(\displaystyle x_n = \sum_{(a1,a2..ak)} a1a2...ak\)
where the sum is over all compositions (a1,a2,....,ak) of n and over all values of k.
Prove that \(\displaystyle x_n = n + \sum_{i=1}^{n-1} i*x_n_-_i\)
This is what I have so far:
\(\displaystyle x_n = \sum_{(a1,a2..ak)} a1a2...ak\)
We can pull out of the composition of just n from the summation, we get get:
\(\displaystyle x_n = n + \sum_{(a1,a2..ak)} a1a2...ak\) (I'm not sure how to show the summation with the 'n' I pulled out)
\(\displaystyle x_n = n + \sum_{1<=a1<=n-1} a1 * \sum_{(a2..ak)} a2...ak\)
do a variable substitution for a1 = i
\(\displaystyle x_n = n + \sum_{i>=1}^{n-1}i * \sum_{(a2..ak)} a2...ak\)
From here I don't know how to show that the second summation is \(\displaystyle x_n_-_i\)
Any help would be great.
Thanks,
John
where the sum is over all compositions (a1,a2,....,ak) of n and over all values of k.
Prove that \(\displaystyle x_n = n + \sum_{i=1}^{n-1} i*x_n_-_i\)
This is what I have so far:
\(\displaystyle x_n = \sum_{(a1,a2..ak)} a1a2...ak\)
We can pull out of the composition of just n from the summation, we get get:
\(\displaystyle x_n = n + \sum_{(a1,a2..ak)} a1a2...ak\) (I'm not sure how to show the summation with the 'n' I pulled out)
\(\displaystyle x_n = n + \sum_{1<=a1<=n-1} a1 * \sum_{(a2..ak)} a2...ak\)
do a variable substitution for a1 = i
\(\displaystyle x_n = n + \sum_{i>=1}^{n-1}i * \sum_{(a2..ak)} a2...ak\)
From here I don't know how to show that the second summation is \(\displaystyle x_n_-_i\)
Any help would be great.
Thanks,
John