The extra problem at the bottom. Please use a proof and also generally break down the premise of the problem so I undestand it. ThanksSoMuch. :)

CS 275, SPRING 2019, HW 4 The Homework is due next Thursday at the very beginning of the class. The work has to be done independently! Problem 1 (3 pts): Write a recursive definition for the sequence ao, a1 Problem 2 (3 pts): How many one-to-one functions are there from a set of cardinality 8 to sets with the following cardinalities? 9! :1.6425 705-)! 251, 5 Problem 3 (4 pts): A palindrome is a string whose re to the string. How many binary strings of length 13 are NOT palindromes? 18 en /2 Extra Problem (3 pts): Let d be a positive integer. Show that among any group of d +1 (not necessarily consecutive) positive integers there are at least two with the same reminder when they are divided by d remalinde