ابتدا فکر کنید شکل قطعات بسته‌بندی شده در شکلات اولیه به چه صورت است.

هر بسته بندی از یک تکه‌ی افقی از سطر اول، یک تکه‌ی افقی از سطر دوم، یا یک ستون عمودی تشکیل شده است.

فرض کنید در یک بسته‌بندی نهایی، مجموعه‌ی $S \in \{1, 2, \dots, n\}$ ستون‌هایی باشد که در بسته‌بندی نهایی آمده‌اند. مستطیل‌های بین این ستون‌ها به چه صورت بسته‌بندی شده است؟

چون در این مستطیل‌ها، هیچ ستونی به شکل کامل در بسته‌بندی نیامده، پس برش اول آن‌ها را به دو سطر تبدیل کرده و یکی از این دو سطر را بسته‌بندی کرده است.

اگر این مسطیل $a\times b$ باشد، حداکثر $2^{b-1}$ حالت مختلف برای بسته‌بندی آن وجود خواهد داشت.

بر اساس تعداد اعضای $S$، یک عبارت غیر صریح برای محاسبه‌ی حداکثر تعداد بسته‌بندی‌ها از روی راهنمایی بالا بسازید.

عبارت غیر صریح راهنمایی فوق: \[ \sum_{k=0}^{n} \binom{n}{k} 2^{n-k} \]

از بسط دو‌جمله‌ای برای یافتن مقدار صریح این عبارت استفاده کنید.

\[ \sum_{k=0}^{n} \binom{n}{k} 2^{n-k} = (1+2)^n = 3^n \]

سعی کنید خانواده‌ای بزرگ از مثال‌های بسته‌بندی ارائه دهید تا حکم ثابت شود.

سعی کنید رابطه بازگشتی‌ای برای شمارش بخشی از بسته‌بندی‌های مطلوب پیدا کنید.

تعداد دسته‌بندی‌ها را برای شکلات‌های $2\times 1$، $2 \times 2$، $2 \times 3$ و $2 \times 4$ حساب کنید.

به کمک محاسبات بخش قبل، در رابطه بازگشتی بر کجا بودن ستون اولی که به عنوان یک تکه‌ی جدا بسته‌بندی شده حالت‌بندی کنید.

تنها حالاتی را در نظر بگیرید که اولین ستون بسته‌بندی شده، یکی از ۵ ستون اول باشد.

اگر $B_n$ را رابطه بازگشتی به تعریف راهنمایی‌های بالا بگیریم، داریم $B_n = B_{n-1}+B_{n-2}+3B_{n-3}+7B_{n-4}+13B_{n-5}$

به استقرا ثابت کنید $B_n \ge c (\frac{5}{2})^n$ و یک $c$ مطلوب بیابید.

چون $f(n) \ge B_n$ پس حکم ثابت می‌شود.