<p>The value of \(\displaystyle\sum_{r=1}^{n+1}\left(\sum_{k=1}^{n} {}^k C_{r-1}\right)\) (where \(r, k, n \in \mathbb{N}\)) is equal to</p>
Step-by-Step Solution
Key Concept: Recognize that the inner sum ∑(k=1 to n) C(k,r-1) counts choosing (r-1) items from sets of sizes 1,2,...,n sequentially, which by the hockey stick identity equals C(n+1,r). The outer sum then becomes ∑(r=1 to n+1) C(n+1,r) = 2^(n+1) - 1.
<p><strong>Step 1:</strong> Evaluate the inner sum using the hockey stick identity.</p><p>For fixed r, we have: ∑(k=1 to n) C(k,r-1)</p><p>Note that C(k,r-1) = 0 when k < r-1, so this sum effectively runs from k=r-1 to n.</p><p>By the hockey stick identity: ∑(k=r-1 to n) C(k,r-1) = C(n+1,r)</p><p><strong>Step 2:</strong> Substitute into the outer sum.</p><p>∑(r=1 to n+1) ∑(k=1 to n) C(k,r-1) = ∑(r=1 to n+1) C(n+1,r)</p><p><strong>Step 3:</strong> Evaluate the outer sum.</p><p>We know that ∑(r=0 to n+1) C(n+1,r) = 2^(n+1)</p><p>Since our sum starts at r=1 (not r=0): ∑(r=1 to n+1) C(n+1,r) = 2^(n+1) - C(n+1,0) = 2^(n+1) - 1</p><p>∴ Answer: <strong>2^(n+1) - 1</strong></p>
Correct Answer: A