Problem Set 3 (PHI 251)\ Due Fri. February 9th by 5 pm Eastern\ Please scan and upload to Blackboard as a pdf; no pictures allowed; feel free\ to also turn in a paper copy to Philosophy Dept, Hall of Languages Room 541\ For EACH problem, label the base case(s) AND label the induction step/hypothesis.\ Call a string over

{a,b}

an "a-palindrome" if it is a palindrome that has "a" as a\ middle letter. (An a-palindrome therefore must have an odd number of letters.)\ (i) Give a recursive definition of the set of "a-palindromes", and\ (ii) prove by induction that every a-palindrome has an even number of "

b

"'s.\ Prove that no well-formed formula of sentential logic ever contains consecutive\ atomic formulas [e.g. nothing like '

(PP&Q)

'.]\ Complete two of the remaining three problems: you get to pick your favorite two!\ Here is the recursive definition of

n

! (read "

n

factorial"):\

1!=1\ (n+1)!=(n+1)\\\\times n!

\ That is,

n!=ubrace((n\\\\times (n-1)\\\\times dots3\\\\times 2\\\\times 1)ubrace)_(n times )

\ Prove by induction: For every

n

greater than or equal to

a,b,c,dn2

Please scan and upload to Blackboard as a pdf; no pictures allowed; feel free to also turn in a paper copy to Philosophy Dept, Hall of Languages Room 541 For EACH problem, label the base case(s) AND label the induction step/hypothesis. 1. Call a string over {a,b} an "a-palindrome" if it is a palindrome that has " a " as a middle letter. (An a-palindrome therefore must have an odd number of letters.) (i) Give a recursive definition of the set of "a-palindromes", and (ii) prove by induction that every a-palindrome has an even number of " b "'s. 2. Prove that no well-formed formula of sentential logic ever contains consecutive atomic formulas [e.g. nothing like ' (PP&Q) '.] Complete two of the remaining three problems: you get to pick your favorite two! 3. Here is the recursive definition of n ! (read " n factorial"): 1!=1(n+1)!=(n+1)n! That is, n!=ntimes(n(n1)321) Prove by induction: For every n greater than or equal to 5,3n1