I am sorry for the triviality of this question, but is this proof of the worst-case complexity of linear search correct?
Claim. Let $L$ be a list of length $n$ and $k$ a target value in $L$. Then in the worse case linear search requires $n$ comparisons to find the value $k$.
Proof. By induction on n.
Base case. If $n=1$ then a single comparison is required because the single element must be $k$. Induction step. Assume that the claim holds for $n$. For $n+1$, it takes 1 comparison to check whether the element $n+1$ is equal to k. If not, then we need to check whether element $((n+1)-1)=n$ is equal to k, which by the induction hypothesis, requires $n$ comparisons. This completes the proof.
Your proof is valid.
Alternative method which is a bit more handwavey (prefer your method as being more rigorous and more clearly correct): if you are searching for value $k$ in a list $L$ but the element is not actually in the list, and you do fewer than $n$ comparisons, there must be an element $l \in L$ you have not compared. We may permute $L$ and pass it to the linear search algorithm again; this gives the result that for any list input, any of its elements could be the one we didn't compare. That means we really do have no information at all about the element we didn't compare: we can't tell whether it's $k$ or not.