Let Hn be defined as follows Hn 0 n LE 0 1 n 1 or n 2 Hn

Let H(n) be defined as follows: H(n) = { 0 n LE 0 {1 n = 1 or n = 2 {H(n - 1) + H(n - 2) - H(n -3) n > 2 Prove that n N, n GE 1 rightarrow H(2n) = H(2n - 1) = n.

Solution

it can be proved by the second principle of mathematical induction.

let us assume that H(2k)=k for all k=1,2,3.......n

take k=n+1 n>2

then H(2n+2)=H(2n+2-1)+H(2n+2-2)-H(2n+2-3)=H(2n+1)+H(2n)-H(2n-1)

                  =[H(2n+1-1)+H(2n+1-2)-H(2n+1-3)]+H(2n)-H(2n-1)

                  =H(2n)+H(2n-1)-H(2n-2)+H(2n)-H(2n-1)

                  =H(2n)+H(2n)-H(2(n-1))

                  =n+n-n [by assumption]

                  =n

H(2n)=n for all n>=2

let us assume that H(2k-1)=k for all k=1,2,3.......n

take k=n+1

then H(2n+1)=H(2n+1-1)-H(2n+1-2)-H(2n+1-3)=H(2n)+H(2n-1)-H(2n-2)

                   =[H(2n-1)+H(2n-2)-H(2n-3)]+H(2n-1)-H(2n-2)=H(2n-1)+H(2n-2)-H(2n-3)+H(2n-1)-H(2n-2)

                    =H(2n-1)+H(2n-1)-H(2n-3)

                    =H(2(n-1)+1)+H(2(n-1)+1)-H(2(n-2)+1)

                    =n+n-n   [by assumption]

                    =n

hence H(2n)=H(2n-1)=n for all n>=2 [proved]