ლექცია 5, ინდუქცია

1) აზმათწესში იყო, ადვილია, უბრალოდ ბევრი წერა უნდა. ის ამოცანაა, 2^n*2^n ზომის იატაკს რომ L ფორმის ფილებით ვფარავთ. თუ არ იცით, კომენტარებში იკითხეთ და დავწერ.



2)ხარი ხართან რომ დააბა.

შეცდომაა ბიჯში. ჩვენ ვაჩვენეთ, რომ ჭეშმარიტია P(1), P(2)->P(3),.......P(n)->P(n+1), მაგრამ P(2) არ შეგვიმოწმებია.

problem 6.1

დაამტკიცე ინდუქციურად:

1^3+2^3+.....+n^3= (n*(n+1)/2)^2

საწერად ბევრია, ასე რომ შინაარსობრივად ავხსნი.
ჯერ შევამოწმებ თუ სრულდება, როცა n=1.
შემდეგ დავუშვებ რომ n-ისთვის სრულდება და შევამოწმებ n+1-s.

1^3+2^3+.....+n^3 + (n+1)^3 = ((n+1)*(n+2)/2)^2

პირველი ნაწილი უდრის  (n*(n+1)/2)^2 - ს:
(n*(n+1)/2)^2 + (n+1)^3 = ((n+1)*(n+2)/2)^2
გავამარტივებთ და ვნახავთ, რომ სწორია.

problem 6.3

წინა ამოცანის ანალოგიურია

problem 6.5

ამოცანაში მოცემულია მცდარი დამტკიცება და უნდა ვიპოვოთ შეცდომა.

შეცდომა ამოცანის "ხარი ხართან რომ დააბა"-ს ანალოგიურია, ინდუქცია არ მუშაობს, როცა k=1.

problem 6.6

მცდარი თეორემა:
ყოველი n>=0 - სთვის, 2+3+4+......n=n(n+1)/2

აქაც ბიჯშია შეცდომა, როცა n=1, გამოდის, რომ 0=1.

problem 6.10

n>=1-ზე. n რაოდენობის კაცი შეგვიძლია დავყოთ 4 ან 7 კაციან ჯგუფებად. რა მნიშვნელობები შეიძლება მიიღოს n-მა?

შინაარსობრივად:
ვამოწმებ ყველა ნატურალურ რიცხვს, სანამ არ მივიღებ ზედიზედ რამდენიმე დამაკმაყოფილებელ რიცხვს, რის შემდეგადაც ინდუქციით ვამტკიცებ, რომ ამ რიცხვებზე დიდი ყოველი რიცხვი დამაკმაყოფილებელია.
გვაწყობს 21-ზე დიდი ნებისმიერი რიცხვი (და რამდენიმე რიცხვი 35-მდე). ამას ვამტკიცებ ასე: თუ n გვაწყობს, მაშინ n+1-იც გვაწყობს, რადგან:
ა)თუ n მიიღება მინიმუმ 1 შვიდიანის გამოყენებით, ამ შვიდიანს შევცვლი 2 ოთხიანით და მივიღებთ n+1-ს.
3)თუ შვიდიანების გარეშე მიიღება, მაშინ 5 ოთხიანს მაინც უნდა შეიცავდეს (21-ზე დიდი რომ იყოს) ამ 5-იდან 4-ს შევცვლით 3 შვიდიანით და მივიღებთ n+1-ს.