Determine whether the statement is true of false. If true, provide a proof. If false provide a counterexample.
for $n \in N, 2n-8 < n^2-8n+17$
I started off like a typical induction proof.
Base Case: n=1
$2(1)-8=-6<(1)^2-8(n)+17 = 10$
which holds.
Inductive Hypothesis
$2n-8 < n^2-8n+17$
Inductive Step
$2(n+1)-8 < (n+1)^2-8(n+1)+17$
$2n-8+2<n^2-6n+10$
Trying to relate the Inductive Step with the Inductive Hypothesis.
$(2n-8) + 2 < (n^2-8n+17)+2n-7$
which means I now need to show when
$2<2n-7$
This part clearly doesn't hold for for an n > 5. So, the inductive hypothesis must be false.
However for any n<5, the inductive hypothesis holds, and fails at n=5 (I couldn't find many other counterexample). giving 2<2 (a contradiction)
I have an exam coming up soon, and I'm trying to determine how to find out how to find counterexamples systematically (or as close to systematically as possible) Is there a way to find at which numbers an inductive proof will fail? This one confuses me because the inductive hypothesis fails at 5, but not 6,7,8 or 100. So how could I actually know to try 5? Because here I just got lucky that it was a number that I plugged in.
This problem can be tackled without induction. The inequality $2n-8 < n^2-8n+17$ is equivalent to $0< n^2-10n+25 = (n-5)^2$. This is true for all $n$ except $n=5$.
In general, if you have an inequality of the type $0<an^2+bn+c$, this is true for all $n$ only if the associated second degree equation does not have a positive integer root.