Mathematical Induction

[Orillion]

Im hoping for some assistance with some Mathematical Induction work im having to do at University.

Im having to show by Induction that given an n-bit binary string, that the number of such strings is equal to 2^n.

Sorry if this isnt the right place to post such a question, but it does relate to Computer Science i guess.

[Yoni]

Do you want to know about mathematical induction in general, or just this specific problem?

To prove this specific problem:

1) Verification for n = 1.
In a 1-bit binary string, there are 2 possible strings, 0 and 1. This is equal to 2^1, or 2^n.

2) Assumption for n = k.
Assume that in a k-bit binary string, there are 2^k possible strings.

3) Proposition for n = k + 1.
In a (k + 1)-bit binary string, there are 2^(k + 1) possible strings.

4) Proof of the proposition (#3).
A (k + 1)-bit binary string can be expressed as one bit followed by a k-bit binary string.
By the assumption (#2), there are 2^k possibilities for the k-bit binary string.
There are 2 possibilities for the extra bit.
Therefore, for the entire (k + 1)-bit binary string, there are 2 * 2^k possibilities, or 2^(k + 1).

Q.E.D.

(Note: I learned mathematical induction in Hebrew, so I might be using "non-standard" terminology - please reply and tell me if I am)

[Adron]

How do you know that combining 2 possibilities and 2^k possibilities makes 2*2^k possibilities or generally, that combining a possibilities and b possibilities makes a*b possibilities? Because looking at the question, that's the only nonobvious part...

If you can assume that possibilities multiply, then if you have n bits, you're combining 2 possibilities n times, i.e. 2*2*2*...*2 n times which by definition is 2^n...

[Orillion]

Thank you both for your help

I've had about 3 lectures on Indunction thus far, as its part of my Discrete mathematics paper and I understand it pretty well. Just my lecturer has thrown us all in the deep end with this assignment.

I do believe you can assume that possibilities multiply together as this appears to be a combination.

If i could ask both for your help with the final question, a bit of trig:

Prove for any natural number cos(n * pi) = (-1)^n

[iago]

The way I figure induction, if I get the right answer to the first question on the exam, and I get the right answer to the next question, they should all be right!  But try telling that to a discrete math professor, they don't like it that much..

[yes, I know the blatent logical flaw is that I'm not proving it for any case x+1, just the case where x = 1 + 1, but I don't care about logic!]

[Orillion]

Well my professor covered most of the topic in an hr or two, which was perhaps too quick. But thats a change from when we learned proposational logic which seemed to take weeks

[Yoni]

Prove for any natural number cos(n * pi) = (-1)^n

cos(0) = 1
cos(pi) = -1

cos(x) = cos(x+2k*pi) for any real x, whole k

For an even n: n = 2k (k is some whole number), (-1)^n = 1
cos(n*pi) = cos(2k*pi) = cos(2k*pi + 2(-k)*pi) = cos(0) = 1 = (-1)^n

For an odd n: n = 2k + 1 (k is some whole number), (-1)^n = -1
cos(n*pi) = cos((2k+1)*pi) = cos((2k+1)*pi + 2(-k)*pi) = cos(pi) = -1 = (-1)^n

[Orillion]

Thanks alot Yoni I think I've started to fully grasp the Induction ideas