Discrete math question

MAT243 Fall2021
PAPERonInductionandStructuralInduction DUEWednesday,Dec1,2021,11:59PM-inCanvas
mandatory-countsas 5% oftheclassgrade
Writecompleteandcorrectproofs. Noneedtotype,but,ifyouprefer,youarecertainlyallowed todoso. Ifyoutypethepaper-youhavetousecorrectmathsymbols!

1. Prove using Mathematical Induction that 42n+1 +52n+1 +62n+1 is divisible by 15, ∀n ≥0.
2. Let a and b be two characters. Define, recursively, a set S of strings by: 1
    ∈ S (where  is the empty string) 2
   if x ∈ S, then xa ∈ S if x ∈ S, then bbx ∈ S, where xa and bbx represents concatenation of strings/characters. Prove, using structural induction, that∀x ∈ S,∃m,n integers, m,n ≥0, so that x = bb···b |{z}2 m times
   aa···a |{z} n times .
3. Define, recursively, the set S: 1
   3∈ S 2
   if n ∈ S, then 4n +2∈ S if n ∈ S, then 3n2 −2∈ S Prove, using structural induction, that for∀n ∈ S,∃k ∈Z, k ≥0, so that n = 11k +3(i.e., n ≡3 (mod 11)