Maths
Akshata Sharma
if f(n+1) = max{ f(k) + f(n-k+1) + 1} for 1 <= k <= n; f(1) = 0.
Find f(n+1) in terms of n.
Eg: f(4) = ? n = 3; 1<= k <= 3; f(4) = max{f(1) + f(3) + 1, f(2) +
f(2)+1, f(3) + f(1) +1}
achille
Why not compute the first few f(i) by hand.
The answer will then become obvious.
Akshata Sharma
f(1)=0
f(2)=max(f(1)+f(1-1+1)+1) = 1
f(3)=max{f(1)+f(2)+1, f(2)+f(1)+1} = 2
f(4)=max{f(1)+f(3)+1, f(2)+f(2)+1, f(3)+f(1)+1} =3
f(5)=max{f(1)+f(4)+1, f(2)+f(3)+1, ....,f(4)+f(1)+1} = 4
f(6)=max{.....} =5
what I can see here is in each f(i), all comma separated expressions
evaluate to the same value. For exampe in f(5), all f(1)+f(4)+1,
f(2)+f(3)+1....evalluate to same value 4.
so is f(n+1)=n?? I am not sure if this pattern changes for large n...
LudovicoVan
As you say, by inspection it is easy to see that the answer is: f(n+1)
= n, for all n. This can be generalized on the base case to: f(n+1) =
(n+1)*f(1) + n. But, how to go to prove such a thing formally?
TIA,
-LV
Rick Decker
> the first few f(i):
>
> f(1)=0
> f(2)=max(f(1)+f(1-1+1)+1) = 1
> f(3)=max{f(1)+f(2)+1, f(2)+f(1)+1} = 2
> f(4)=max{f(1)+f(3)+1, f(2)+f(2)+1, f(3)+f(1)+1} =3
> f(5)=max{f(1)+f(4)+1, f(2)+f(3)+1, ....,f(4)+f(1)+1} = 4
> f(6)=max{.....} =5
>
> what I can see here is in each f(i), all comma separated expressions
> evaluate to the same value. For exampe in f(5), all f(1)+f(4)+1,
> f(2)+f(3)+1....evalluate to same value 4.
> so is f(n+1)=n?? I am not sure if this pattern changes for large n...
>
to bet you've recently been taught a proof technique that would work
well here.
Regards,
Rick
William Hughes
Gosh you would need a technique that works on infinite sets!
Whatever could it be?
- William Hughes
William Hughes
If "taught" implies "have learned" I would take that bet.
- William Hughes
LudovicoVan
I do have thought about induction: but all I can manage to think of is
a proof that the solution found by inspection is indeed correct.
(Plus, I seem to need to split the proof in two sub-cases for even vs
odd n's, and not that I would be sure I could actually write such a
proof to the end...)
But, again, I'd need to know/guess the solution in advance to follow
that line: so, I was wondering if there is something like a
"calculation" that would find the correct solution without any need
for previous inspection... (The main difficulty for the beginner I am
is of course in dealing with that 'max' over a set, which I cannot see
how to reduce to some form of direct calculation: and this is why this
problem is interesting to me...)
-LV
David Bernier
> the first few f(i):
>
> f(1)=0
> f(2)=max(f(1)+f(1-1+1)+1) = 1
> f(3)=max{f(1)+f(2)+1, f(2)+f(1)+1} = 2
> f(4)=max{f(1)+f(3)+1, f(2)+f(2)+1, f(3)+f(1)+1} =3
> f(5)=max{f(1)+f(4)+1, f(2)+f(3)+1, ....,f(4)+f(1)+1} = 4
> f(6)=max{.....} =5
>
> what I can see here is in each f(i), all comma separated expressions
> evaluate to the same value. For exampe in f(5), all f(1)+f(4)+1,
> f(2)+f(3)+1....evalluate to same value 4.
> so is f(n+1)=n?? I am not sure if this pattern changes for large n...
Have you passed the Turing Test yet?
David
--
"isn't quotable" isn't quotable.
Ilmari Karonen
> On Feb 16, 7:33 pm, achille <achille_...@yahoo.com.hk> wrote:
>> On Feb 16, 10:01 pm, Akshata Sharma <akshatasharm...@gmail.com> wrote:
>>
>> > please help..
>>
>> > if f(n+1) = max{ f(k) + f(n-k+1) + 1} for 1 <= k <= n; f(1) = 0.
>> > Find f(n+1) in terms of n.
>>
>> The answer will then become obvious.
>
>
> f(1)=0
> f(2)=max(f(1)+f(1-1+1)+1) = 1
> f(3)=max{f(1)+f(2)+1, f(2)+f(1)+1} = 2
> f(4)=max{f(1)+f(3)+1, f(2)+f(2)+1, f(3)+f(1)+1} =3
> f(5)=max{f(1)+f(4)+1, f(2)+f(3)+1, ....,f(4)+f(1)+1} = 4
> f(6)=max{.....} =5
>
> what I can see here is in each f(i), all comma separated expressions
> evaluate to the same value. For exampe in f(5), all f(1)+f(4)+1,
> f(2)+f(3)+1....evalluate to same value 4.
> so is f(n+1)=n?? I am not sure if this pattern changes for large n...
If you're not sure, why not try to prove it?
Specifically, there are three steps to this kind of proof:
1. Guess a rule for f(k) in terms of k. You've already done this.
2. Verify that the rule holds for k = 1. This should be easy.
3. Assume that the rule holds for all 1 <= k < n. Try to prove that
it must then also hold for k = n.
BTW, there's a specific name for proofs like this. As someone else
already suggested, you've probably been recently taught about them.
--
Ilmari Karonen
To reply by e-mail, please replace ".invalid" with ".net" in address.
Ray Vickson
Just as a matter of interest: the usual induction axiom is: S(1) and
{S(k) implies S(k+1)} implies S(n) for all n. Here we want: S(1) and
{S(j) for all j in {1,2,...,k} implies S(k+1)} implies S(n) for all n.
Is this a theorem of Peano arithmetic? Of course, it is perfectly
"obvious".
R.G. Vickson
Ilmari Karonen
> On Feb 16, 9:57 am, Ilmari Karonen <usen...@vyznev.invalid> wrote:
>>
>> Specifically, there are three steps to this kind of proof:
>>
>> 1. Guess a rule for f(k) in terms of k. You've already done this.
>>
>> 2. Verify that the rule holds for k = 1. This should be easy.
>>
>> 3. Assume that the rule holds for all 1 <= k < n. Try to prove that
>> it must then also hold for k = n.
>
> Just as a matter of interest: the usual induction axiom is: S(1) and
> {S(k) implies S(k+1)} implies S(n) for all n. Here we want: S(1) and
> {S(j) for all j in {1,2,...,k} implies S(k+1)} implies S(n) for all n.
> Is this a theorem of Peano arithmetic? Of course, it is perfectly
> "obvious".
Surely you just need to define
R(n) <=> (S(k) for all 1 <= k <= n)
and then do induction on R.
Ray Vickson
> On 2011-02-16, Ray Vickson <RGVick...@shaw.ca> wrote:
>
>
>
> > On Feb 16, 9:57 am, Ilmari Karonen <usen...@vyznev.invalid> wrote:
>
> >> Specifically, there are three steps to this kind of proof:
>
> >> 1. Guess a rule for f(k) in terms of k. You've already done this.
>
> >> 2. Verify that the rule holds for k = 1. This should be easy.
>
> >> 3. Assume that the rule holds for all 1 <= k < n. Try to prove that
> >> it must then also hold for k = n.
>
> > Just as a matter of interest: the usual induction axiom is: S(1) and
> > {S(k) implies S(k+1)} implies S(n) for all n. Here we want: S(1) and
> > {S(j) for all j in {1,2,...,k} implies S(k+1)} implies S(n) for all n.
> > Is this a theorem of Peano arithmetic? Of course, it is perfectly
> > "obvious".
>
> Surely you just need to define
>
> R(n) <=> (S(k) for all 1 <= k <= n)
>
> and then do induction on R.
Yes, of course (he says, as he slaps his forehead).
R.G. Vickson