In the inductive step, it needs to prove that, if\(P\left( k \right)\)is true, then\(P\left( {k + 1} \right)\)is also true.
That is,\(P\left( k \right) \to P\left( {k + 1} \right)\)is true for all positive integers k.
In the inductive hypothesis, we assume that\(P\left( k \right)\)is true for any arbitrary positive integer\(k\)
That is,at least \(k + 1\) lines are needed to cover the lattice points with \(x \ge 0\), \(y \ge 0\),and \(x + y \le k\).
Now it must have to show that\(P\left( {k + 1} \right)\)is also true.
To prove this let’s consider a triangle of the lattice points defined as\(x \ge 0\), \(y \ge 0\),and \(x + y \le k + 1\).
For construction assume we need only\(k + 1\)line to cover this region.
So, these lines must cover the \(k + 2\)points on the line \(x + y = k + 1\).
But the line \(x + y = k + 1\) itself only can cover more than one of these points, because we know that two distinct lines can intersect at most one point.
Therefore, none of the \(k + 1\) lines which are assumed in inductive hypothesis needed to cover the set of lattice points within the triangle but not on this line can cover more than one of the points on this line, and this leaves at least one
point uncovered. Therefore, our assumption is wrong and at least \(k + 2\) lines are needed to cover the lattice points with \(x \ge 0\), \(y \ge 0\), and \(x + y \le k + 1\).
From the above, we can see that\(P\left( {k + 1} \right)\)is also true.
Hence,\(P\left( {k + 1} \right)\)is true under the assumption that\(P\left( k \right)\)is true. This
completes the inductive step.
Using mathematical induction it is shown that at least\(n + 1\) straight lines are needed to ensurethat every lattice point\(\left( {x,y} \right)\)with\(x \ge 0\),\(y \ge 0\), and\(x + y \le n\)lies on one of these lines.
