[Boards: 3 / a / aco / adv / an / asp / b / biz / c / cgl / ck / cm / co / d / diy / e / fa / fit / g / gd / gif / h / hc / his / hm / hr / i / ic / int / jp / k / lgbt / lit / m / mlp / mu / n / news / o / out / p / po / pol / qa / r / r9k / s / s4s / sci / soc / sp / t / tg / toy / trash / trv / tv / u / v / vg / vp / vr / w / wg / wsg / wsr / x / y] [Home]
how would you prove f(n) = a[sub]n using...
Images are sometimes not shown due to bandwidth/network issues. Refreshing the page usually helps.

You are currently reading a thread in /sci/ - Science & Math

File: in.jpg (961 KB, 1691x1000) Image search: [iqdb] [SauceNao] [Google]
961 KB, 1691x1000
how would you prove f(n) = a[sub]n using induction?

for a problem like f(n) = 2^n -1, and a[n] = 2*a[n-1]+1, a[1]=1?

i proved a 2 base cases, n=1, n=2, to both be true. i don't get how you prove f(k+1) = a[k+1] though..
>>
>>7586202
a[n] = 2^n-1 = 2*2^(n-1)-1 = 2*2^(n-1) -2+2-1 = 2( 2^(n-1) -1 ) +1 = 2*a[n-1]+1
>>
>>7586243
how much practice does it take to see something like this? i was doing scrap work for probably an hour after finishing the base cases and couldnt find anything close to this...
>>
>>7586256
>>7586243
>>7586243
>2( 2^(n-1) -1 ) +1 = 2*a[n-1]+1
is wrong..
>2( 2^(n-1) -1 ) +1 = 2*(a[n]-1)+1
a[n] is a sequence, not a function
>>
Don't know if you're still looking at this op but I'm going to share a bit of info with you that might make the whole thing seem less mystical...

f(n) = a sub n

the function here returns values, right? And the value returned depends the value inserted, correct? Aassuming this is correct let's move on to the next piece.

a sub n is an indexing notation, therefore it results in a column table of values { n, n+1, n+2, n+3, etc. } otherwise known as a set. n, here, is the index and depending on what value you used as n will return the value at that particular index. Unless arbitrarily stated, a set is derived from the values a function returns, right? So then maybe we can say that this indexed array is the array that holds the values to the function f( n ) and we assert that statement using f( n ) = a sub n.

lemme make a pic related for you and then post back.
>>
>>7586325
***and depending on what NUMBER you used as n will return the value at that particular index.
>>
whoops lemme finish this, like the whole thinking it up, before I send it to you so I don't feel like such a fucking idiot. Segmentation fault between my function and my array.
>>
>>7586259
You must be confused, sequences are functions.
>>
>>7586336
Yeah that's where I got confused. I'm filling the table and using arrows to explain the relationship so that he can get the answer himself too. I don't want to demonstrate the correct method, I want him to learn it through a full logical discourse that he can use if it suits him.
>>
>>7586339
OK, but I don't think that correspondence is the source of his confusion. It seems to be the algebra that he was stuck on.
>>
To my anonymous induction teacher, I'm the n! > (n+1/2)^n guy and I'm not OP.
>>
>>7586346
>n! > (n+1/2)^n
That's obviously false.
>>
>>7586342
I think not realizing the correspondence is the fault of the matter, though,

How could he not understand that adding 1 to the value of a function would add 1 to the set values that correspond to that function if he understands that the correspondence is based on the values themselves.

if I add one to the value here, it's the same as adding one to value in the array that holds my values. The math is what guides that logic and if he doesn't have it, it's about time he fucking figured it out.
>>
File: mostlyright.jpg (559 KB, 1486x1391) Image search: [iqdb] [SauceNao] [Google]
559 KB, 1486x1391
Now I didn't get into doing the problems themselves because frankly its fucking annoying to do them in paint but I'll see about writing them out and then posting them up.

Basically the last part leads into using k in place of n, modifying the equations so that that values returned show a direct relationship that can be said to exist between the k in the exponential form and the k in the index form ( because after all we can't reach the index form ) We need a way to make sure that the modifications taking place as changes in one side are reflected in the new value set as those modifications are made to the other side. So, making the original equation k on one side and doing that same thing to the other side will gives us the same table again.

Once we've ascertained that a modification will be reflected in both the index and exponent side we have proved through a process of induction that the two are equal.

It makes sense too if you think about the meaning of the word induction, where something shares a bit of itself for another thing to use as a point of reference.

Consider the relationship between your left and right arm as you use each arm to reach into your left pocket. The left arm simply moves up and down ( index notation ) and the right arms reaches across and then drops into the pocket. How could prove to someone that you were reaching into the same pocket if is possible that you have two pockets? You would have to prove that you indeed stretched your right arm over to the left and pulled out the same things you would with your left hand. I think you can do the rest.
>>
Please ignore the part below the equations and in the fancy brackets. I had originally wrote that in and then moved in for a different explanation and then forgot to delete the bottom part that has a ( : )

I'll check back in a bit to see if you got it right. Btw, I wanted to keep writing but I got blocked a bit.

At the end where I use the arms as an example, the person that needs it proven to them could use the weight of the item as the value in question so the logic doesn't leak into OBLIVION! and leave you wondering what could possibly fit there. It's things like that that keep me from being super Mr. Peabody at math and leads me to procrastinating with League of Legends.
>>
>>7586346
>literally wrong for n=1
>trying to do induction on false premise
"shig"
>>
>>7586441
LOL HAHAHA those values in the table are wrong. I'm pretty sure that's part of the problem, right?
>>
>>7586684
No wait, no they're not.

[Boards: 3 / a / aco / adv / an / asp / b / biz / c / cgl / ck / cm / co / d / diy / e / fa / fit / g / gd / gif / h / hc / his / hm / hr / i / ic / int / jp / k / lgbt / lit / m / mlp / mu / n / news / o / out / p / po / pol / qa / r / r9k / s / s4s / sci / soc / sp / t / tg / toy / trash / trv / tv / u / v / vg / vp / vr / w / wg / wsg / wsr / x / y] [Home]
[Boards: 3 / a / aco / adv / an / asp / b / biz / c / cgl / ck / cm / co / d / diy / e / fa / fit / g / gd / gif / h / hc / his / hm / hr / i / ic / int / jp / k / lgbt / lit / m / mlp / mu / n / news / o / out / p / po / pol / qa / r / r9k / s / s4s / sci / soc / sp / t / tg / toy / trash / trv / tv / u / v / vg / vp / vr / w / wg / wsg / wsr / x / y] [Home]