CS702 Assignment No.1 Solution & Commment, Due Date: 19th November , 2016

CS702: Advanced Algorithm Analysis and Design

Assignment No.1                     MS (CS), Fall 2016                    Maximum Points: 50

Due Date: 19^th November, 2016

Instructions

     

The purpose of this assignment is to give you hands on practice. It is
expected that students will solve the assignments themselves. Following
rules will apply during the evaluation of assignment.

v  Cheating from any source will result in zero marks in the
assignment.

v  Any student found cheating in any of the two assignments submitted
will be awarded "F" grade in the course.

v  No assignment after due date will be accepted

Question No. 1 (25 Points)

The sequence < un > is defined by the recurrence

You have initial condition u1 = 1:

Now you have to show un in terms of Fibonacci / Lucas numbers.

Question No. 2 (25 Points)

Prove the following by induction.