Home /
Expert Answers /
Advanced Math /
please-help-solve-d-and-e-question-1-determine-if-each-of-the-following-conjectures-could-be-p-pa933

Please help solve (d) and (e)

Question 1. Determine if each of the following conjectures could be proven with weak induction or if you would need strong induction and explain your reasoning. Also, tell how many base cases would need to be proven. Note: You do not have to actually prove them! (a) Let $T(N)=T(N?1)+3$ and $T(1)=1$. Conjecture: $T(N)=3N?2$ for all $N?1$. (b) Let $T(N)=2T(N?1)+1$ and $T(1)=1$ Conjecture: $T(N)=2_{N}?1$ for all $N?1$. (c) Let $T(N)=T(N?2)+5$ and $T(1)=1$ and $T(2)=6$ Conjecture: $T(N)?25N+2?$ for all $N?1$. (d) Let $T(N)=T(N?2)+N$ and $T(1)=1$ and $T(2)=2$ Conjecture: $T(N)?2N?(2N?+1)$ for all $N?1$. (e) Let $T(N)=T(floor(N/2))+1$ and $T(1)=1$ Conjecture: $T(N)?1+gN$ for all $N?1$.