מהו מספר הוקטורים הטרנריים באורך n אשר בהם ההפרש בין כל שתי ספרות סמוכות הוא 1 בדיוק?
אני מנסה לפתור את התרגיל הנ"ל. ניסיתי להפריד לשני מיקרים - במקרה הראשון, הוקטור מתחיל באפס או בשתיים ובמקרה השני הוקטור מתחיל באחד. עם זאת, אני מצליח להבין כיצד אני צריך להמשיך בכל תת-מקרה.
אשמח לעזרה 
נתבונן בוקטור טרנרי שבו ההפרש בין שתי ספרות סמוכות הוא 1 בדיוק.
נשים לב כי אם הספרה במקום ה-i בוקטור היא 1, אזי הספרה הבאה חייבת להיות 0 או 2 (שכן אם הספרה הבאה הייתה 1 הינו מקבלים הפרש 0). אם הספרה הבאה היא 0 אז הספרה אחריה חייבת להיות 1 וכך גם אם הספרה הבאה היא 2 (כדי לשמור על הפרש 1 בין הספרות הסמוכות). עתה נפריד לשני מיקרים:
א. הוקטור מתחיל ב-0 או ב-2. במקרה זה, הספרה הבאה חייבת להיות 1 ולאחר מכן 0 או 2 וכך האלה. במילים אחרות, נוכל להסיק כי בכל המקומות הזוגיים תופיע הספרה 1 ואילו במקומות האי-זוגיים תופיע הספרה 0 או 2. נפריד לתת-מיקרים:
- אם n זוגי, אז יש \frac{n}{2} מקומות שבהם מופיע 1 ו- \frac{n}{2} שבהם מופיע 0 או 2.
- אם n אי-זוגי, אז יש \frac{n-1}{2} מקומות שבהם מופיע 1 ו- \frac{n+1}{2} שבהם מופיע 0 או 2.
נוכל להכליל ולהגיד כי יש \lceil\frac{n}{2}\rceil מקומות בהם מופיע 0 או 2. כמו כן, נשים לב כי עבור המקומות הזוגיים יש רק אפשרות אחת ואילו עבור המקומות האי-זוגיים יש 2 אפשרויות (0 או 2). לכן, נוכל להסיק כי יש 2^{\lceil\frac{n}{2}\rceil} אפשרויות לבנות את הוקטור.
ב. הוקטור מתחיל ב-1. במקרה זה, הספרה הבאה חייבת להיות 0 או 2 ולאחר מכן 1 וכך האלה. במילים אחרות, נוכל להסיק כי בכל המקומות האי-זוגיים תופיע הספרה 1 ואילו במקומות הזוגיים יופיע 0 או 2. נפריד לתת-מיקרים:
- אם n זוגי, אז יש \frac{n}{2} מקומות שבהם מופיע 1 ו- \frac{n}{2} שבהם מופיע 0 או 2.
- אם n אי-זוגי, אז יש \frac{n+1}{2} מקומות שבהם מופיע 1 ו- \frac{n-1}{2} שבהם מופיע 0 או 2.
נוכל להכליל ולהגיד כי יש \lfloor\frac{n}{2}\rfloor מקומות בהם מופיע 0 או 2. כמו כן, נשים לב כי עבור המקומות האי-זוגיים יש רק אפשרות אחת ואילו עבור המקומות הזוגיים יש 2 אפשרויות (0 או 2). לכן, נוכל להסיק כי יש 2^{\lfloor\frac{n}{2}\rfloor} אפשרויות לבנות את הוקטור.
בסה"כ ע"פ עקרון החיבור נקבל כי מספר הוקטורים הטרנריים באורך n אשר בהם ההפרש בין כל שתי ספרות סמכות הוא 1 בדיוק הינו:
2^{\lceil\frac{n}{2}\rceil}+2^{\lfloor\frac{n}{2}\rfloor}