Question

(Proof by Induction Problem - Solution included but I still am confused)

Question (with solution): http://f.imgtmp.com/OPRWj.jpg

What confuses me is that there are three letters b, k and n. Normally, these problems only have an n and a k. The n being the variable and the k being a constant plugged into n and then I attempt to show that it works for k+1 but here the b throws me off completely. If I pretend k is a variable and then make b the constant number, then that makes more sense but why is the definition of T(n) being used? If you aren't sure what I'm asking, tell me and I'll elabor

Answer 1

elaborate.

Answer 2

in this setup they are just changing n into k for an arbitrary integer and then assigning k=0 to establish a basis step

Answer 3

then they say since k=0 works then choose some other k such that k=b ... or the k+1 part that we all know and love

Answer 4

Ok, that's different then what I usually do which is just plugin in 0 or whatever the first number is into the n but I get the first post you made.

Answer 5

than*

Answer 6

ok so k is an arbitrary constant and we choose it to have value b?

Answer 7

that seems redundant

Answer 8

proofs do seem rather redundant yes; but its all for a good cause :)

Answer 9

why not just say n (the varaible) is equal to any number denoted as k

Answer 10

pascal was keen to notice that people liked to use words to mean different things and decided that if you could not have a rigoroous way of defining/proving your concepts that your concepts had no value

Answer 11

the way in which people go about making their proofs rigorous can be confusing, but as long as the logic flows from start to finish we consider it valid lol

Answer 12

lol well, does that mean my way is wrong?

Answer 13

wrong? no, just different way to "look" at it

Answer 14

k = 0, b = any int greater than 0 so it satisifies b=k+1

Answer 15

(just plugging in some k for n and showing the k+1 stuff)

Answer 16

not to butt in (ok to butt in) it is not clear why they used "b" in this case. you usually say "for all k < n" then prove it for n by reducting to the case n - 1

Answer 17

sorry my computer lagged

Answer 18

I never did it as k < n but rather n = k. and then assuming that's true and showing n=k+1

Answer 19

best bet, do it your way and see if its proofified :)

Answer 20

lol "proofified". my way is the same mechanically but the assumptions, etc differ.

So, basically what this solution is doing is saying "the variable is n, we choose any number k and show that the equation T(2^k) = 3^(k+1) - 2^(k+1) will hold so we then we say that the number k is equal to the number b (which is useless and redundant) and then we prove that n=k+1=b+1 works and then all is good?

Answer 21

Sorry if I am being redundant lol :P

Answer 22

Actually, wait, I think I am starting to get it.