@howtechstuffworks:
Your question seems to be - why 'k+1' and not 'k+2' or 'k+3' or
something else.
The simple reason is that,
Given that P('k') and P('k+1') is true, we can extend it for ANY value
of k.
(ie) k+2 , can be derived from 'k+1' by substituting k=k+1.
similarly k+3 can be derived from 'K+1' by substituting k=k+1
twice..
The reason thus is that, there ANY INTEGER can be expressed in terms
of its consecutive integer (consecutive - differ by ONE). that is why
k+ 'ONE' is chosen for proving so that the induction works for all
numbers.
(Assuming u prove for P(k+2) as true as in your claim, you cannot
derive P(k+1) as true from these statements by substituting k=k+2..
And if your prove truth for P(2k) as claimed by you, then numbers
which are NOT even, cannot be expressed in the form 2k by substituting
int value for k.)
If you prove P(3k), then numbers which are NOT multiples of 3 cannot
be expressed in the form 3k by substituting integer value for k)
so, k+1 becomes the natural choice so that all possible values greater
than the base case are considered. Hope that helps.
On Jun 13, 9:29 am, HowTechStuffWorks <howtechstuffwo...@gmail.com>
wrote:
> Thanks, Gene. That was an very thoughtful example. I have one more
> doubt like, what we are trying to prove here. That the example will
> work for all numbers(all natural numbers, not only for an multiple of
> two or three or some number) or this example will work for all
> possible(infinite) numbers.
>
> Regarding the Trees problem, since the initial value is one and all
> the tree down will have an even number of child say 2^i till the leaf.
> Isn't it possible to prove based on the theorm, that an odd number +
> even number is always an odd number. Also we can reduce it to the form
> that number of elements is given by the formula, (2^k-1). 2^anything =
> even; even-1 = odd;
>
> If I do by mathematical Induction,
>
> base case : k = 1; value = 1;
>
> kth step : kth step (2^k-1)
> k+1th step : (2^k+1)-1 => (2^k.2)-1; //////////// what are we
> proving here? and how are we verifying it????
>
> When I tried to apply some numbers for the value, I came across this
> thought.
> k = 0; value = 1
> k = 3; Value = 8
> k+1 = 4 Value = 16 => this can be derived from (2^k+1)-1 => (2^k .
> 2^1)-1 => (8.2) -1 => 15
>
> But I am not sure how to proceed with the abstract inductive step and
> I am not sure what we are trying to prove.
>
> Also why we always want to prove the k+1 th step??? why not k+2th or K
> +i th step????
>
> Also can you give me some example where the induction fails.
>
> Thank you very much.
>
> On Jun 12, 11:15 pm, Gene <gene.ress...@gmail.com> wrote:
>
>
>
>
>
>
>
> > Suppose you want to prove that you can climb all the way to the top of a
> > ladder. One way to do this is in two parts: First prove you can stand on
> > the bottom step. Call this step 1 and number the rest of the steps 2,3,..N
> > upward to the top of the ladder.
>
> > The second part is to prove that if you are on any step K, you know how to
> > take one step upward to step K+1. (I'm not telling you how to do that here.
> > But suppose you know how.) This is called the "inductive step." (Pun
> > intended.)
>
> > The principle of indication is that these two proof parts taken together
> > provide the desired proof.
>
> > In this case, the proof is constructive. (This isn't always true.) You
> > effectively get an algorithm for climbing the ladder as a byproduct of
> > proof: Stand on the first step 1. Now use the inductive step with K=1 to
> > get to step K+1 = 2. Use it again with K=2 to get to K+1=3. Continue using
> > N-1 times. This puts you at the top of the ladder.
>
> > Note that in computer science you often need more complex kinds of induction
> > - for example over data structures - rather than integers. For a simple
> > example, take induction over trees. Prove that complete binary trees (where
> > all nodes are either leaves or have 2 children) always have an odd total
> > number of nodes.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
