Question

Can someone help explain this induction?

Answer 1

http://mathforum.org/library/drmath/view/52268.html

Answer 2

first one?

Answer 3

The one the doctor answers with

Answer 4

I don't know where he got The generating function is

(x+x^2+x^3+x^4+....)^4

Answer 5

and prety much anything below that. I've done induction in school before but i'm not sure how he can up with that

Answer 6

lol i just read it 4 times and got stuck exactly where you did

Answer 7

Unless you know how to induct that formula your own way? The one with 2^(x-1)?

Answer 8

no not at all
i have an idea of what a generating function is, it is a function, usually a power series, whose coefficients are a particular sequence
why the one given is the generating function is unclear to me

Answer 9

my only suggestion is to google whatever you were googling again, and see if you can come up with a more detailed proof

Answer 10

or ask someone smarter than me

Answer 11

im pretty sure that was the only one since its rare that partition would include order

Answer 12

is there anyway to prove it without induction?

Answer 13

a better answer i think is here
http://math.stackexchange.com/questions/31562/number-of-ordered-partitions-of-integer
where they show (or tell you how to show) that \(P(n+1)=2P(n)\)

Answer 14

so from there i'm suppose to plug in n+1 into the according two formulas of what u wrote?

Answer 15

they didn't actually use induction but they give the correct formulas?

Answer 16

they do use induction
if you assume that \(P(n)=2^{n-1}\) then showing that \(P(n+1)=2p(n)\) shows that that \(p(n+1)=2^n\)

Answer 17

pretty clever actually, now that i more or less understand the proof

Answer 18

im a little confused on (i) last element 11 and (ii) last element bigger than 11.

Answer 19

it is similar to proving that the number of subsets of a set of n element is 2^n`

Answer 20

the line that says


If the last element is 1, remove it, and you get an ordered partition of n. Moreover, all ordered partitions of n arise in this way, for any ordered partition of n can be extended to an ordered partition of n+1 by appending a 1. So there are P(n) ordered partitions of n+1 with last element 1

??

Answer 21

it makes sense to me, does it make sense to you?

Answer 22

i think this would make a lot more sense if you use an example

Answer 23

ok lets do a simple one
list the ordered partitions of 4, and then the ordered partitions of 5

Answer 24

4=(4) (1+1+1+1) (2+2) (1+2+1)(1+1+2) (2+1+1)(3+1) (1+3) (8 ways)

5=(5) (4+1) (1+4) (3+2) (2+3) (1+1+3)(1+3+1)(3+1+1) (1+1+1+2)(1+2+1+1)(1+1+2+1)(2+1+1+1) (2+2+1) (2+1+2)(1+2+2)(1+1+1+1+1)

16 ways

Answer 25

wow you are quick

Answer 26

so now let us assume (without counting) that there are 8 ordered partitions of 4

Answer 27

im doing a research paper so i already had that for some base cases lol

Answer 28

ok

Answer 29

take away all the ordered partitions of 5 that end in a 1

Answer 30

ok not take them away, list them

Answer 31

(4+1)(3+1+1)(1+2+1+1)(1+1+2+1)(2+1+1+1)(2+2+1)(1+1+1+1+1)

Answer 32

think you missed at least one

Answer 33

(1+3+1)(3+1+1)

Answer 34

(4+1)(3+1+1)(1+3+1)(1+2+1+1)(1+1+2+1)(2+1+1+1)(2+2+1)(1+1+1+1+1)

Answer 35

how many we got?

Answer 36

8 i repeated one

Answer 37

ok
now eliminate the last 1 for each of those

Answer 38

(4)(3+1)(1+3)(1+2+1)(1+1+2)(2+1+1)(2+2)(1+1+1+1)

Answer 39

exactly
they are the partitions of 4

Answer 40

nice i just noticed that

Answer 41

could you add one's to get partition of 5,6,7 etc?

Answer 42

none are missed, and all the partitions of 5 that end in a 1 are generated by tacking a 1 on the end of those

Answer 43

lol lets not get ahead of ourselves here

Answer 44

lol i just wanted to see if it worked as a general rule or if its only backwards

Answer 45

to better understand this

Answer 46

we are only comparing partitions of 5 with partitions of 4

Answer 47

so to understand the general statement made in the explanation

Answer 48

this statement
If the last element is 1, remove it, and you get an ordered partition of n. Moreover, all ordered partitions of n arise in this way, for any ordered partition of n can be extended to an ordered partition of n+1 by appending a 1. So there are P(n) ordered partitions of n+1 with last element 1
is more or less clear now right?

Answer 49

so in the example n+1 was 5 and n=4?

Answer 50

yes

Answer 51

we did it by example
listed all partitions of 5,
listed the ones that ended in a 1
removed the 1
see that we get exactly the partitions of 4

Answer 52

so whats the other case when the element is greater than 1?

Answer 53

that is even easier
we already know there that P(4) =2^3 partitions of 5 that end in a 1
now how about the ones that don't end it a 1, how many of those?

Answer 54

to list them, take all the partitions of 4, and add a 1 to the last number

Answer 55

only for the ones greater than 1 on the last element right?

Answer 56

no

Answer 57

take all the partitions of 4
here
(4) (1+1+1+1) (2+2) (1+2+1)(1+1+2) (2+1+1)(3+1) (1+3)

Answer 58

add a 1 to the last number

Answer 59

oh you get 8 partitions of 5

Answer 60

(5),(1+1+1+2),(2+3) (1+2+2)m (1+1+3), (2+1+2), (3+2), (1+4)

Answer 61

ignore the m

Answer 62

those are all the partitions of 5 that do NOT end in a 1

Answer 63

and there are clearly P(4)=2^3 of those as well

Answer 64

so P(4) partitions of 5 that end in a 1, and p(4) partitions that do not end in a 1, for a total of 2p(4) partitions all together

Answer 65

from your listed partitions of (5),(1+1+1+2),(2+3) (1+2+2)m (1+1+3), (2+1+2), (3+2), (1+4), if we had added the 1 without simplifying out the term we would get the other 8 terms right?

Answer 66

i am not sure what you are asking
what i did was take the 8 partitions of 4 and added a 1 to the last number, to get another 8 partitions of 5 that do not end in 1

Answer 67

oh i see what you are saying, yes

Answer 68

such as (4), add 1 to get (5) if we leave it at (4+1), its all the other missing partitions?

Answer 69

oh ok

Answer 70

add one, get 8 partitions of 5, append a 1 at the end, get another 8, right

Answer 71

good way to think about it

Answer 72

so i basically do get their statement now but where they used induction

if you assume that P(n)=2^(n−1) then showing that P(n+1)=2p(n)

shows that that p(n+1)=2n

is this ever interpretted like a sum formula?

Answer 73

but then again a sum formula would not serve much of a purpose i think

Answer 74

im not sure if knowing the sum of the powers helps prove anything

Answer 75

you are thinking too hard maybe
if you assume \[P(n)=2^{n-1}\] and prove that \[P(n+1)=2P(n)\] then that automatically shows \[P(n+1)=2^n\]

Answer 76

ok typo there

Answer 77

\[P(n+1)=2P(n)=2\times 2^{n-1}=2^n\]

Answer 78

oh true true

Answer 79

\[P(n+1)=2P(n)=2\times \overbrace{2^{n-1}}^{\text{induction here}}=2^n\]

Answer 80

but in my class's induction we usually get a sum formula in that we add then sum of maybe p(n+1)+2pn=2p(n+1) something of that sort

Answer 81

and we see that its alike on both sides

Answer 82

induction is induction
there are lots of ways to get to what you want, it doesn't have to be a summation formula

Answer 83

let me clue you in on something, that they do not tell you when they teach induction

Answer 84

yeah i think im generally good with this part. my research also consists of wheather partition (order or not) works with non-whole numbers or negative numbers like you can get a specific formula

Answer 85

im assuming none are possible but im suppose to know why

Answer 86

negatives i just researched and they undefined apparently

Answer 87

don't ask me
as for induction,you are taught with examples that are more or less trivial
it is usually some simple algebra to go from the case of n to n + 1
in fact you don't need induction to prove summation formulas (but that is a different story)
later on you will see that the hard part of induction is not to do some algebra to get what you want, but to figure out how (or why) you can reduce from the case of n + 1 to the case of n
this is trivial in summation formulas, you just omit the last term in the sum

Answer 88

you see we were sort of stuck with that here
you have a partition of n + 1, how do you compare it to a partition of n
that was the hard part
it gets harder

Answer 89

i think your induction explanation was pretty good and i should be ok with that in my paper but is there a general statement of why negative partition can't work ?

Answer 90

now you are out of my league, i have no idea
in fact i didn't even know this until i googled

Answer 91

i think i already see why there would be an infinite amount of partitions for every negative number

Answer 92

i do like the other explanation as well
there are n - 1 spaces between n rocks
there are \(2^n\) subsets of a set of n-1 spaces, same as partitioning the n rocks

Answer 93

oops i meant \(2^{n-1}\) must be getting tired
good luck with your research

Answer 94

this was the majority of my paper so you basically saved my night with your explanation. might actually get decent sleep, thank you again sir

Answer 95

you are quite welcome
it is great to help someone actually engaged in mathematics
as apposed to say "find the line..."