Art of Mathematics

21 Januari 2008

Barisan rekursif bersuku kuadrat

Diarsipkan di bawah: Teori Bilangan — Tag:, , , , — Johan @ 18.16

[IMO 1986 longlist] Barisan bilangan (a_n)_{n\in\mathbb{N}_0} didefinisikan a_0=a_1=1 dan a_{n+2}=7a_{n+1}-a_n-2 untuk n\ge1. Buktikan bahwa a_n selalu bilangan kuadrat untuk setiap n.

Solusi
Dengan memeriksa beberapa kasus awal, a_2=4, a_3=25, a_4=169. Bandingkan ini dengan barisan Fibonacci, didefinisikan F_1=F_2=1, F_{n+2}=F_{n+1}+F_n. Dapat dilihat pada suku-suku awal bahwa a_n=F_{2n-1}^2. Kita akan buktikan ini dengan induksi.

Pernyataan ini telah dibuktikan benar untuk n=1, 2, 3, 4. Maka kita dapat mengasumsikan a_k=F^2_{2k-1} untuk setiap k\le n, lalu akan dibuktikan a_{n+1} adalah bilangan kuadrat. Dari persamaan a_n=7a_{n-1}-a_{n-2}-2 dan a_{n+1}=7a_n-a_{n-1}-2, kurangkan persamaan pertama dari persamaan kedua:

a_{n+1}-a_n=7a_n-a_{n-1}-2-7a_{n-1}+a_{n-2}+2

Sederhanakan menjadi

a_{n+1}=8a_n-8a_{n-1}+a_{n-2}=8F^2_{2n-1}-8F^2_{2n-3}+F^2_{2n-5}

Saya akan buktikan bahwa F_{m-2}=3F_m-F_{m+2}.

Ruas kiri

F_{m-2}=F_m-F_{m-1}

Ruas kanan adalah

3F_m-F_{m+2}=3F_m-F_{m+1}-F_m=2F_m-F_m-F_{m-1}=F_m-F_{m-1}

Maka terbukti bahwa F_{m-2}=3F_m-F_{m+2}, sehingga F_{2n-5}=3F_{2n-3}-F_{2n-1}.

Persamaan tadi menjadi

a_{n+1}=8F^2_{2n-1}-8F^2_{2n-3}+(3F_{2n-3}-F_{2n-1})^2.

Sederhanakan menjadi

a_{n+1}=F_{2n-3}^2-6F_{2n-3}F_{2n-1}+9F_{2n-1}^2=(F_{2n-3}-3F_{2n-1})^2=F_{2n+1}^2.

Maka terbukti.

2 Komentar »

  1. saya gak ngerti bahasanya, bracha…
    apaan sih itu..

    Komentar oleh ^^^***~~~~~~~-- - - -... . . — 24 Januari 2008 @ 20.44

    Balas

  2. Soal ini memang agak sulit. IMO adalah olimpiade matematika internasional yang sangat sulit. Setiap tahun, setiap negara mengirim soal yang disebut longlist. Dari longlist, diseleksi menjadi shortlist. Maka dari itu soal ini cukup sulit.

    Padahal di blog ini saya tidak mengepost soal yang benar-benar sulit. Tapi jika belum berpengalaman, memang sulit mencernanya.

    Komentar oleh Johan — 25 Januari 2008 @ 16.50

    Balas

RSS umpan untuk komentar-komentar dalam tulisan ini. URI Lacak Balik

Tinggalkan komentar

Blog pada WordPress.com.