رابطه‌ی بازگشتی، اشتباه کجا است؟ سطح۱

مساله
یک رشته‌ی n حرفی از عددهای صفر و یک و دو داریم. هدف این است که تعداد رشته‌هایی را پیدا کنیم که تعداد صفرهای آنها فرد باشد.

تلاش می‌کنیم تا رابطه‌ای بازگشتی پیدا کنیم. در آغاز رشته‌ای از صفر و یک و دو، که تعداد صفرهای آن فرد باشد را فردگرا می‌نامیم. پس تعداد رشته‌های n حرفی فردگرا را f_n می‌نامیم و رشته‌ی n تایی فردگرا را از روی رشته‌ی n-1 تایی فردگرا می‌سازیم.
اگر یک رشته‌ی n-1 تایی فردگرا داشته باشیم به سادگی می‌توانیم به ابتدای آن یک «1» یا یک «2» اضافه کنیم تا یک رشته‌ی n تایی فردگرا بسازیم. اما رشته‌ی n تایی فردگرا جور دیگری هم ساخته می‌شود. به این ترتیب که یک رشته‌ی n-1 تایی غیر فردگرا داشته باشیم (یعنی تعداد صفرهای آن فرد نباشد، بلکه زوج باشد.) و به ابتدای آن یک «0» اضافه کنیم. در این صورت تعداد صفرها در این رشته‌ی غیر فردگرا که زوج بود فرد خواهد شد و اکنون این رشته‌ی n تایی فردگرا است. از طرفی به سادگی روشن است که تعداد همه‌ی رشته‌های n تایی از 0 و 1 و 2 برابر با 3ⁿ است و تعداد رشته‌های n-1 تایی غیر فردگرا برابر با 3^n-1-f_n-1 است. پس رابطه‌ی بازگشتی را پیدا کرده‌ایم و داریم:

f_n=2f_n-1 + 3^n-1 - f_n-1 = f_n-1 + 3^n-1

از بخت خوب ما پیدا کردن رابطه‌ای صریح بر حسب n در این جا کار ساده‌ای است. همین رابطه‌ی بازگشتی را دوباره و دوباره می‌نویسیم تا به چنین رابطه‌ای برسیم:

f_n = f_n-1 + 3^n-1
= f_n-2 + 3^n-2 + 3^n-1
= f_n-3 + 3^n-3 + 3^n-2 + 3^n-1
= 3⁰ + 3¹ + 3² + ... + 3^n-3 + 3^n-2 + 3^n-1

و محاسبه‌ی این مجموع نیز به کمک اتحاد جبری

xⁿ - 1 = (x - 1) (x⁰ + x¹ + x² + ... + x^n-3 + x^n-2 + x^n-1)

بسیار سرراست خواهد بود و داریم:

f_n = 3⁰ + 3¹ + 3² + ... + 3^n-3 + 3^n-2 + 3^n-1 = (3ⁿ - 1) / (3 - 1) = (3ⁿ - 1) / 2

شاید اکنون بد نباشد که وسوسه شویم تا تعداد رشته‌های n تایی زوجگرا را نیز پیدا کنیم. یعنی تعداد رشته‌های n تایی از 0 و 1 و 2 که در آن‌ها تعداد صفرها زوج باشد. مساله بسیار شبیه مساله‌ی پیشین است و کار ساده‌ای در پیش دایم.
باز هم تلاش می‌کنیم تا رابطه‌ای بازگشتی پیدا کنیم. تعداد رشته‌های n حرفی زوجگرا را z_n می‌نامیم و رشته‌ی n تایی زوجگرا را از روی رشته‌ی n-1 تایی زوجگرا می‌سازیم.
اگر یک رشته‌ی n-1 تایی زوجگرا داشته باشیم به سادگی می‌توانیم به ابتدای آن یک «1» یا یک «2» اضافه کنیم تا یک رشته‌ی n تایی زوجگرا بسازیم. اما رشته‌ی n تایی زوجگرا جور دیگری هم ساخته می‌شود. به این ترتیب که یک رشته‌ی n-1 تایی غیر زوجگرا داشته باشیم (یعنی تعداد صفرهای آن زوج نباشد، بلکه فرد باشد.) و به ابتدای آن یک «0» اضافه کنیم. در این صورت تعداد صفرها در این رشته‌ی غیر زوجگرا که فرد بود زوج خواهد شد و اکنون این رشته‌ی n تایی زوجگرا است. از طرفی به سادگی روشن است که تعداد همه‌ی رشته‌های n تایی از 0 و 1 و 2 برابر با 3ⁿ است و تعداد رشته‌های n-1 تایی غیر زوجگرا برابر با 3^n-1-z_n-1 است. پس رابطه‌ی بازگشتی را پیدا کرده‌ایم و داریم:

z_n=2z_n-1+ 3^n-1-z_n-1=z_n-1+ 3^n-1

و با کمک گرفتن چند باره از همین رابطه‌ی بازگشتی و همان اتحاد جبری خواهیم داشت:

z_n = 3⁰ + 3¹ + 3² + ... + 3^n-3 + 3^n-2 + 3^n-1 = (3ⁿ - 1) / (3 - 1) = (3ⁿ - 1) / 2

ولی حواستان هست که قطعا اشتباه کرده‌ایم؟


تعداد رشته‌های فردگرا و تعداد رشته‌های زوجگرا را برابر پیدا کرده‌ایم! مگر چنین چیزی شدنی است؟ هر رشته‌ی n تایی یا فردگرا است یا زوجگرا است، حالت سومی نداریم. یعنی تعداد صفرهای یک رشته‌ی n تایی از 0 و 1 و 2 بالاخره یا عددی زوج است یا عددی فرد است. بنا بر این جمع تعداد این دو جور رشته باید برابر تعداد کل رشته‌های n تایی از 0 و 1 و 2 بشود که پیش‌تر یادآور شدیم که این تعداد برابر با 3ⁿ است ولی مجموع این دو مقداری که ما پیدا کرده‌ایم چیز دیگری است. ببینید:

f_n = (3ⁿ - 1) / 2 و z_n = (3ⁿ - 1) / 2 => f_n + z_n = 3ⁿ - 1

در شلوغی محاسبات یکی از رشته‌ها را گم کرده‌ایم! فکر کنید. کجا اشتباه کرده‌ایم؟