 Igen. Amire eredetileg gondoltam, az lényegében ezt a gondoltatmenetet csomagolja be, és egyáltalán nem induktív.
Legyen harmadik komplex egységgyök, azaz . Most csak annyira lesz szükségünk, hogy létezik olyan szám, melyre 2+ +1=0.
Jelöljük fk(n)-nel azon n-jegyű pozitív egészek számát, amelyek k maradékot adnak 3-mal osztva. Ekkor mivel nyilván 3=1, ezért a= a+3b tetszőleges a,b egész számokra. Emiatt meggondolhatjuk, hogy

Utóbbi összeg viszont nyilván nem más, mint ( 2+ 3+ 7+ 9)n, ahol 2+ 3+ 7+ 9= 2+1+ +1=1. Vagyis
f0(n)+f1(n) +f2(n) 2-1=0.
Ez egy -ban másodfokú egyenlet; megoldásai: és 2. Viszont x2+x+1 is olyan másodfokú polinom, melynek gyökei és 2, ezért a két szóban forgó polinom igazából egymás többszöröse. Ebből adódik, hogy f0(n)-1=f1(n)=f2(n), ahol viszont f0(n)+f1(n)+f2(n)=4n, ezért .
-
A fent leírt módszer általánosabb feladatok megoldására is alkalmas: például keressük meg, hány n-jegyű számnak lesznek a számjegyei 1,3,4,5,6,9 kozüliek, és 7-tel oszthatók.
Egy másik gyakorló feladat például a következő. Hány p-elemű részhalmaza van az {1,2,...,2p} halmaznak, melynek elemeinek összege p-vel osztható, ahol p páratlan prímszám?
(De ezek már tényleg nem ujjgyakorlatok.)
|