%%%%%%%%%%%%%%%%%%%%% PACKAGE IMPORTS %%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt]{article}
\usepackage{amsmath, amsfonts, amsthm, amssymb}
\usepackage{lmodern}
\usepackage{microtype}
\usepackage{fullpage}
\usepackage{romannum}

\usepackage[x11names, rgb]{xcolor}
\usepackage{graphicx}
\usepackage{circuitikz}
\usetikzlibrary{decorations,arrows,shapes}

\usepackage{etoolbox}
\usepackage{enumerate}
\usepackage{enumitem}
\usepackage{listings}
\usepackage{array}
\usepackage{probsoln}

%%%%%%%%%%%%%%%%%%%%%%%% QUESTION # %%%%%%%%%%%%%%%%%%%%%%%%
%% This part helps number your questions and creates a    %%
%% new page with each question for the aesthetics.        %%
%% It also creates parts that helps you answer questions  %%
%% To use do: \begin{question} ... \end{question}         %%
%% and: \begin{part} ... \end{part}                       %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setlength{\parindent}{0pt}
\setlength{\parskip}{5pt plus 1pt}

\providetoggle{questionnumbers}
\settoggle{questionnumbers}{true}
\newcommand{\noquestionnumbers}{
    \settoggle{questionnumbers}{false}
}

\newcounter{questionCounter}
\newenvironment{question}[2][\arabic{questionCounter}]{%
    \addtocounter{questionCounter}{1}%
    \ifnum\value{questionCounter}=1 {} \else {\newpage}\fi%
    \setcounter{partCounter}{0}%
    \vspace{.25in} \hrule \vspace{0.5em}%
        \noindent{\bf \iftoggle{questionnumbers}{Question #1: }{}#2}%
    \vspace{0.8em} \hrule \vspace{.10in}%
}

\newcounter{partCounter}[questionCounter]
\renewenvironment{part}[1][\alph{partCounter}]{%
    \addtocounter{partCounter}{1}%
    \vspace{.10in}%
    \begin{indented}%
       {\bf (#1)} %
}{\end{indented}}

\def\indented#1{\list{}{}\item[]}
\let\indented=\endlist
\def\show#1{\ifdefempty{#1}{}{#1\\}}

%%%%%%%%%%%%%%%%%%%%%%%% SHORT CUTS %%%%%%%%%%%%%%%%%%%%%%%%
%% This is just to improve your quality of life. Instead  %%
%% of having to type long things, you can type short      %%
%% things. Ex: \IMP instead of \rightarrow to get ->      %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\IMP{\rightarrow}
\def\AND{\wedge}
\def\OR{\vee}
\def\BI{\leftrightarrow}
\def\DIFF{\setminus}
\def\SUB{\subseteq}

\newcolumntype{C}{>{\centering\arraybackslash}m{1.5cm}}
\renewcommand\qedsymbol{$\blacksquare$}

%%%%%%%%%%%%%%%%%%%%%%%%%%% TITLE %%%%%%%%%%%%%%%%%%%%%%%%%%
%% This is shows the homework number, your name, your     %%
%% collaborators, and the day. If you'd prefer to not so  %%
%% your name, just comment out the "\maketitle" below     %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{\vspace{-2cm}Homework 6\vspace{-0.3cm}}
\author{Insert Your Name}
\date{\vspace{-0.3cm}\today\vspace{-1cm}}

%%%%%%%%%%%%%%%%%%%%%%%% WORK BELOW %%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\maketitle

%%%%%% QUESTION 1 %%%%%
\begin{question}{Collaborators}
% Please list your collaborators here; or state that you worked alone.

\end{question}

%%%%%% QUESTION 2 %%%%%
\begin{question}{Induction and sums [10 points]}
Prove that, for every positive integer $n$, the following equality is true
\[
 6 \cdot \sum_{k=1}^n k^2 = n(2n^2+3n+1)
\]

\begin{solution}
    \begin{description}
            \item[Base Case.]
            \item[Induction Hypothesis.]
            \item[Induction Step.]
\begin{align*}

\end{align*}
	\item [Conclusion.]
        \end{description}

\end{solution}

\end{question}

%%%%%% QUESTION 3 %%%%%
\begin{question}{Induction Divides [20 points]}

Prove that $7\mid (8^n-1)$ for all $n \in \mathbb{N}$, by induction on $n$.

Hint: In your inductive step, you'll need to be creative to apply your inductive hypothesis. Focus on forcing the right expression to appear. \\

\begin{solution}
    % Enter your solution here...
    \begin{description}
            \item[Base Case.]
            \item[Induction Hypothesis.]
            \item[Induction Step.]
\begin{align*}

\end{align*}
	\item [Conclusion.]
        \end{description}

\end{solution}

\end{question}


%%%%%% QUESTION 4 %%%%%
\begin{question}{Induction Code [20 Points]}
Consider the following code snippet.

\begin{verbatim}
public int Mystery(int n){
    if(n < 0)
        throw new InvalidInputException();
    if(n == 0)
        return 2;
    if(n == 1)
        return 7;
    return Mystery(n-1) + 2*Mystery(n-2);
}
\end{verbatim}

Use strong induction to show that \texttt{Mystery(n)}$=3\cdot 2^n + (-1)^{n+7}$ for all integers $n \geq 0$. \\

\begin{solution}
    % Enter your solution here...
    \begin{description}
            \item[Base Case.]
            \item[Induction Hypothesis.]
            \item[Induction Step.]
\begin{align*}

\end{align*}
	\item [Conclusion.]
        \end{description}

\end{solution}

\end{question}

%%%%%% QUESTION 5 %%%%%
\begin{question}{Well that just doesn't sound right [8 points]}
Consider the following (very incorrect) induction proof:

\textcircled{1} Let $P(n)$ be ``$5n = 0$''\\
We show $P(n)$ holds for all $n \in \mathbb{N}$ by induction on $n$.

\textcircled{2} Base Case: $n=0$\\
If $n=0$ then $5n = 5\cdot 0 = 0$, so $P(0)$ is true.

\textcircled{3} Inductive Hypothesis: Suppose $P(n)$ holds for $n=0,\ldots,k$ for an arbitrary integer $k\geq 0$

\textcircled{4} Inductive Step: \\
\textcircled{A} We want to prove $P(k+1)$ is true, i.e. $5(k+1) = 0$. \\
\textcircled{B} Observe that $5(k+1) = 5(s) + 5(t)$. for integers $s,t$ with $0\leq s<k+1$ and $0\leq t<k+1$.\\
\textcircled{C} Applying the inductive hypothesis twice, we have $5s=0$ and $5t = 0$.\\
\textcircled{D} Substituting both into the original equation, we get: $5(k+1) = 0 + 0$, so $5(k+1) = 0$, as required. \\
\textcircled{5} The result follows for all $n \geq 0$ by induction.

\begin{enumerate}
	\item Find the smallest counterexample to the claim that $P(n)$ holds for all $n\in \mathbb{N}$. [3 points]
	You should both (1) show that your example is a counterexample and (2) argue why all smaller natural numbers are not counterexamples.
	\begin{solution}
    % Enter your solution here...
    
    \end{solution} 

    \item Clearly identify the flaw in the proof; it will help to run through the proof with your smallest counterexample.
	For ease of explanation, we've taken the (unusual) step of labelling every sentence. [5 points]
	\begin{solution}
    % Enter your solution here...
    
    \end{solution}
\end{enumerate}

\end{question}

%%%%%% QUESTION 6 %%%%%
\begin{question}{Running Times [20 Points]}

You wrote a piece of recursive code. On an input of size $n$, your function takes $T(n)$ time to run, where:
     \begin{align*}
         T(n) &= 5n &\text{if } 1 \leq n \leq 4\\
         T(n) &= T\left(\lfloor n/2 \rfloor\right) + T\left( \lfloor n/4 \rfloor \right) + 5n &\text{for all } n > 4
     \end{align*}
     In the definition above, $\lfloor x \rfloor$ is the ``floor'' function; it returns the greatest integer less than or equal to $x$.\\
     For example: $\lfloor 3.2 \rfloor = 3$, $\lfloor 3.7 \rfloor = 3$, $\lfloor 3 \rfloor = 3$.

     Show that for all $n\in \mathbb{N}$ with $n \geq 1$, $T(n)\leq 20n$

     Hint 1: Notice that while $T()$ is defined with equality, you are only proving an inequality.\\
     Hint 2: The only fact about the floor function you will need is $\lfloor x \rfloor$ is an integer and $x-1 < \lfloor x \rfloor \leq x$. \\
     
\begin{solution}
    % Enter your solution here...
    \begin{description}
            \item[Base Case.]
            \item[Induction Hypothesis.]
            \item[Induction Step.]
\begin{align*}

\end{align*}
	\item [Conclusion.]
        \end{description}

\end{solution}

\end{question}

%%%%%% QUESTION 7 %%%%%
\begin{question}{str000ng induction would be a good choice [20 points]}

Let $0^n$ mean a string of $n$ zeros. Let $S$ be the set of strings defined as follows:

\textbf{Basis Steps:} $0^3 \in S$, $0^5 \in S$\\
\textbf{Recursive Step:} If $0^x, 0^y \in S$ then $0^x \cdot 0^y \in S$ where $\cdot$ is string concatenation.

Show that, for every integer $n\geq 12$ the set $S$ contains the string $0^n$.

{\color{red}\textbf{Caution:}} Structural Induction is not the best tool for this problem. Structural induction shows $\forall x.\, x \in S \rightarrow P(x)$.
You're analyzing what the elements of $S$ are in this problem, not proving a predicate holds for all elements of $S$. \\

\begin{solution}
    % Enter your solution here...
    \begin{description}
            \item[Base Case.]
            \item[Induction Hypothesis.]
            \item[Induction Step.]
\begin{align*}

\end{align*}
	\item [Conclusion.]
        \end{description}

\end{solution}

\end{question}

%%%%%% QUESTION 8 (EXTRA CREDIT) %%%%%
%%%%%% DELETE IF YOU ARE NOT DOING THIS PROBLEM) %%%%%
\begin{question}{Extra Credit: Sticks And Stones}

Consider an infinite sequence of positions $1,2,3,\dots$ and suppose we have a stone at position  $1$ and another stone at position $2$. In each step, we choose one of the stones and move it according to the following rule: Say we decide to move the stone at position $i$; if the other stone is not at any of the positions $i+1,i+2,\dots,2i$, then it goes to $2i$, otherwise it goes to $2i+1$.

\hspace{1.5em} For example, in the first step, if we move the stone at position 1, it will go to 3 and if we move the stone at position 2 it will go to 4.  Note that, no matter how we move the stones, they will never be at the same position.

\hspace{1.5em} Use induction to prove that, for any given positive integer $n$, it is possible to move one of the stones to position $n$. For example, if $n=7$ first we move the stone at position $1$ to $3$. Then, we move the stone at position $2$ to $5$  Finally, we move the stone at position $3$ to $7$. \\

\begin{solution}
% Enter your solution here...

\end{solution}

\end{question}

%%%%%% FEEDBACK %%%%%
\begin{question}{Feedback}
\begin{part}{How many hours did you spend working on this assignment?} %% (a) %%
\end{part}

\begin{part}{Which problem did you spend the most time on?} %% (b) %%
\end{part}

\begin{part}{Which problem did you find to be the most confusing?} %% (c) %%
\end{part}

\begin{part}{Any other feedback for us?} %% (d) %%
\end{part}

\end{question}

\end{document}
