Recursion Q

function f is defined on the set of positive integers by
f(1) = 1
f(2n) = 2f(n)
n f(2n + 1) = (2n+1)(f(n) +n) for all n>= 1
prove that f(n) is always an integer.

Reply 1

tweetybiiiiird20

OP

10

Original post by tweetybiiiiird20

function f is defined on the set of positive integers by
f(1) = 1
f(2n) = 2f(n)
n f(2n + 1) = (2n+1)(f(n) +n) for all n>= 1
prove that f(n) is always an integer.

This isnt HW or anything I just suck at proofs

Reply 2

DFranklin

18

Original post by tweetybiiiiird20

This isnt HW or anything I just suck at proofs

What have you tried so far?

Reply 3

Kurren

Are you familiar with proof by strong induction?

Reply 4

DFranklin

18

Original post by Kurren

Are you familiar with proof by strong induction?

Let's not suggest methods until the OP's at least shown they've put in some thought of their own...

Reply 5

tweetybiiiiird20

OP

10

Original post by DFranklin

What have you tried so far?

since f2(n) is double f(n) for all n from 1
2f(1) = f(2) = 2
2f(3) = f(6)
I expanded out the second part (which I probably should have and got integers apart from f(n) / n which I couldn’t prove is divisible. Another thing I was trying was perhaps if I substitute for f(n) in the second line to get f(2n)/2
nf(2n+1) = (2n+1)(f(2n)/2 + n)
nf(2n+1) = (nf(2n) + 2n^2 + f(2n)/2 + n)
nf(2n+1) = (2nf(n) + 2n^2 + f(n) + n)
Should I equate and go from there?
sorry for the long reply I’ve just been trying everything

Reply 6

tweetybiiiiird20

OP

10

Original post by Kurren

Are you familiar with proof by strong induction?

I know how to use proof by induction but I’ve never tried it in this context :frown:

is there a difference between induction and “strong” induction?

Reply 7

mqb2766

21

Original post by tweetybiiiiird20

since f2(n) is double f(n) for all n from 1
2f(1) = f(2) = 2
2f(3) = f(6)
I expanded out the second part (which I probably should have and got integers apart from f(n) / n which I couldn’t prove is divisible. Another thing I was trying was perhaps if I substitute for f(n) in the second line to get f(2n)/2
nf(2n+1) = (2n+1)(f(2n)/2 + n)
nf(2n+1) = (nf(2n) + 2n^2 + f(2n)/2 + n)
nf(2n+1) = (2nf(n) + 2n^2 + f(n) + n)
Should I equate and go from there?
sorry for the long reply I’ve just been trying everything

You seem to have the bones of what you want to prove, but its not very clear. A few things Id do/think about
1) work out f(1), f(2), f(3), f(4), f(5), f(6)... that can help make clear what you want to prove (and maybe how to go about it)
2) Youve identified that f(n) being divisble by n is a key part of the proof. If you did some form of inductive argument, what would you be showing? How would you go about it
3) The induction/strong induction distinction is relatively simple. Induction is to assume true for N then show N+1. Strong induction is to assume true for all <=N, then show N+1. Hopefully 1) and 2) would indicate which would be the most use here.

(edited 1 year ago)

Reply 8

DFranklin

18

Just to add to the post above: instead of using induction, a fairly common pattern for a question like this is to use a particular form of proof by contradiction:

"Suppose it's not true. Pick N to be the *smallest* value for which it fails." and then show that it can't fail for N without there being a smaller values for which it fails.

[Thus is basically equivalent to strong induction, but I often find it somehow feels more natural].

(edited 1 year ago)

Reply 9

tweetybiiiiird20

OP

10

Original post by DFranklin

Just to add to the post above: instead of using induction, a fairly common pattern for a question like this is to use a particular form of proof by contradiction:

"Suppose it's not true. Pick N to be the *smallest* value for which it fails." and then show that it can't fail for N without there being a smaller values for which it fails.

[Thus is basically equivalent to strong induction, but I often find it somehow feels more natural].

I dont really get this though. just because it doesnt fail for n = 1 how do i know it won't fail for larger n?

Reply 10

mqb2766

21

Original post by tweetybiiiiird20

I dont really get this though. just because it doesnt fail for n = 1 how do i know it won't fail for larger n?

Did you do an inductive proof? If so, the "reverse" would be to do something like an infinite descent proof
https://en.wikipedia.org/wiki/Proof_by_infinite_descent
So assume f(2n), f(2n+1) is not an integer, what does that mean for f(n)? You could then make the argument that you iterate back to f(1)=1 or make the argument that 2n or 2n+1 was the first term which was not an integer in order to get a contradiction.