Can I prove $T(k)=T(k+1)=k$?

Question

I'm proving algorithm to justify using inductive hypothesis.
$T(k)$ is the minimum round value the number of handshaking within $N=k$ people.

If $T(k-2)=T(k-1)=k-2$, can I prove about $T(k)$?

I used proof by inductive hypothesis.

1) Base case, $N=3, N=4$

T(3) = minimum number of handshaking within 3 people is 3
T(4) = minimum number of handshaking within 4 people is 3

2) Inductive Hypothesis ($k$ is odd number)

Until $N=k-1$, it is true that $T(k-2)=T(k-1)=k-2$.

3) Prove when $N=k$

How can I prove?

If you can throw some more light about what $T(x)$ is and be more precise to what you're saying, it will be easier to answer. — PradyumanDixit, Oct 09 '18 at 04:57

score 1 · Answer 1 · answered Oct 09 '18 at 05:07

1

Letting n = k - 1, then T(n-1) = T(n) = n - 1.

If this is going to be true for any n, there is a contradiction in this statement. For example, take n = 5 just to show this. You said:

$$ T(5 - 1) = T(4) = 5 - 1 = 4 \\ T(5) = 5 - 1 \\ \therefore T(4) = t(5) = 4 $$

Then if you do this for n = 6, then:

$$ T(6-1) = T(5) = 6 - 1 = 5 \\ T(6) = 6 - 1 = 5 \\ \therefore T(6) = T(5) = 5 $$

In the top example, T(5) = 4 and in the bottom T(5) = 5. Therefore, your original statement can't be possible; its impossible for both $T(n-1)$ and $T(n)$ to be equal to $n - 1 $

answered Oct 09 '18 at 05:07

user2662833

1,958

I edited and added more information, $k$ is odd number. Can u see it? – baeharam Oct 09 '18 at 05:11
If k is an odd number, then k+1 is even isn't it? – user2662833 Oct 09 '18 at 05:19
Because $k$ is odd, $n$ must be even, but you used 5 as $n$ in the first equation. – baeharam Oct 09 '18 at 05:39
That doesn't change anything, you can use n=6 and n=7 and prove the same thing. Can you post the original question from the source you got it from? – user2662833 Oct 09 '18 at 09:19
I mean $n$ can only be even number, you don't have to use $n=7$ – baeharam Oct 09 '18 at 10:44

Can I prove $T(k)=T(k+1)=k$?

1 Answers1